广州网站设计推荐刻,创建网站代码是什么,对单位网站的要求,网站建设要求 牛商网题目#xff1a;
蒜头君在玩一款逃生的游戏。在一个 nmn \times mnm 的矩形地图上#xff0c;蒜头位于其中一个点。地图上每个格子有加血的药剂#xff0c;和掉血的火焰#xff0c;药剂的药效不同#xff0c;火焰的大小也不同#xff0c;每个格子上有一个数字#xff0…题目
蒜头君在玩一款逃生的游戏。在一个 n×mn \times mn×m 的矩形地图上蒜头位于其中一个点。地图上每个格子有加血的药剂和掉血的火焰药剂的药效不同火焰的大小也不同每个格子上有一个数字如果格子上的数字是正数说明是一个药剂代表增加的生命值如果是负数说明是火焰代表失去的生命值。
蒜头初始化有 v 点血量他的血量上限是 c任何时刻他的生命值都不能大于血量上限如果血量为 0 则会死亡不能继续游戏。
矩形地图上的四个角(1,1)(1,m)(n,1)(n,m) 为游戏的出口。游戏中只要选定了一个出口就必须朝着这个方向走。例如选择了左下的出口就只能往左和下两个方向前进选择了右上的出口就只能往右和上两个方向前进左上和右下方向的出口同理。
如果成功逃生那么剩余生命值越高则游戏分数越高。为了能拿到最高分请你帮忙计算如果成功逃生最多能剩余多少血量如果不能逃生输出−1。
输入格式
第一行依次输入整数 nnmmxxyyvvcc1n,m≤10001≤x≤n1≤y≤m1≤v≤c≤10000nnmmxxyyvvcc1 n,m \leq 10001 \leq x \leq n1 \leq y \leq m1 \leq v \leq c \leq 10000nnmmxxyyvvcc1n,m≤10001≤x≤n1≤y≤m1≤v≤c≤10000, 其中 n, mn,m 代表地图大小(x, y)(x,y) 代表蒜头君的初始位置vv 代表蒜头的初始化血量cc 代表蒜头的生命值上限。
接下来 nn 行每行有 mm 个数字代表地图信息每个数字的绝对值不大于 100地图中蒜头君的初始位置的值一定为 0。
输出格式
一行输出一个数字代表成功逃生最多剩余的血量如果失败输出 -1−1。
输出时每行末尾的多余空格不影响答案正确性
要求使用「文件输入输出」的方式解题输入文件为 escape.in输出文件为 escape.out
样例输入
4 4 3 2 5 10 1 2 3 4 -1 -2 -3 -4 4 0 2 1 -4 -3 -2 -1
样例输出
10
分析
这里需要分开枚举四个方向。另外还需要处理一个问题中途当遇到某个 dp[i][j] 小于等于 0 的时候把 dp[i][j]赋值为 -inf可以让这个位置就不会转移出后继状态了。当 dp[i][j]大于 c 的时候需要把 dp[i][j]dp[i][j] 赋值为 c(题目中说他的血量上限是 c任何时刻他的生命值都不能大于血量上限)
AC代码
#includestdio.h
#includestring.h
#includealgorithm
#includeiostream
using namespace std;
const int M1e310;
const int inf0x3f3f3f3f;
int n,m,x,y,v,c;
int mp[M][M],dp[M][M];
int main(){freopen(escape.in, r, stdin);freopen(escape.out, w, stdout);cinnmxyvc;for(int i1;in;i)for(int j1;jm;j)cinmp[i][j];dp[x][y]v;for(int ix;i1;i--)for(int jy;j1;j--){if(ixjy) continue;else if(ix) dp[i][j]dp[i][j1]mp[i][j];else if(jy) dp[i][j]dp[i1][j]mp[i][j];else dp[i][j]max(dp[i1][j],dp[i][j1])mp[i][j];if(dp[i][j]0)dp[i][j]-inf;if(dp[i][j]c)dp[i][j]c;}for(int ix;in;i)for(int jy;jm;j){if(ixjy) continue;else if(ix) dp[i][j]dp[i][j-1]mp[i][j];else if(jy) dp[i][j]dp[i-1][j]mp[i][j];else dp[i][j]max(dp[i-1][j],dp[i][j-1])mp[i][j];if(dp[i][j]0)dp[i][j]-inf;if(dp[i][j]c)dp[i][j]c;}for(int ix;in;i)for(int jy;j1;j--){if(ixjy) continue;else if(ix) dp[i][j]dp[i][j1]mp[i][j];else if(jy) dp[i][j]dp[i-1][j]mp[i][j];else dp[i][j]max(dp[i-1][j],dp[i][j1])mp[i][j];if(dp[i][j]0)dp[i][j]-inf;if(dp[i][j]c)dp[i][j]c;}for(int ix;i1;i--)for(int jy;jm;j){if(ixjy) continue;else if(ix) dp[i][j]dp[i][j-1]mp[i][j];else if(jy) dp[i][j]dp[i1][j]mp[i][j];else dp[i][j]max(dp[i1][j],dp[i][j-1])mp[i][j];if(dp[i][j]0)dp[i][j]-inf;if(dp[i][j]c)dp[i][j]c;}int kmax(max(dp[1][1],dp[n][m]),max(dp[1][m],dp[n][1]));if(k0) cout-1endl;else coutkendl;return 0;
}
