蒜头君在玩一款逃生的游戏。在一个 n×m的矩形地图上，蒜头位于其中一个点。地图上每个格子有加血的药剂，和掉血的火焰，药剂的药效不同，火焰的大小也不同，每个格子上有一个数字，如果格子上的数字是正数说明是一个药剂代表增加的生命值，如果是负数说明是火焰代表失去的生命值。
蒜头初始化有 v 点血量，他的血量上限是c，任何时刻他的生命值都不能大于血量上限，如果血量为 0 则会死亡，不能继续游戏。
矩形地图上的四个角(1,1)，(1,m)，(n,1)，(n,m)为游戏的出口。游戏中只要选定了一个出口，就必须朝着这个方向走。例如，选择了左下的出口，就只能往左和下两个方向前进，选择了右上的出口，就只能往右和上两个方向前进，左上和右下方向的出口同理。
如果成功逃生，那么剩余生命值越高，则游戏分数越高。为了能拿到最高分，请你帮忙计算如果成功逃生最多能剩余多少血量，如果不能逃生输出 ?1。
输入格式
第一行依次输入整数 n，m，x，y，v，c（1
接下来 n 行，每行有 m 个数字，代表地图信息。（每个数字的绝对值不大于100，地图中蒜头君的初始位置的值一定为0）
输出格式
一行输出一个数字，代表成功逃生最多剩余的血量，如果失败输出 ?1。
样例输入
4 4 3 2 5 10
1 2 3 4
-1 -2 -3 -4
4 0 2 1
-4 -3 -2 -1
样例输出
10
#include
using namespace std;
int n, m, x, y, v, c;
int tu[1001][1001];
int dp[1001][1001];
int main()
{
cin >> n >> m >> x >> y >> v >> c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> tu[i][j];
}
dp[x][y] = v;
//左上
for (int i = x; i > 0; i--)//下来
for (int j = y; j > 0; j--)//右来
{
if (i == x && j == y)//跳过初始位置
continue;
else if (i == x)//同行(只能从右边移动过来[j+1])
dp[i][j] = tu[i][j] + dp[i][j + 1];
else if (j == y)//同列,只能从下面过来[i+1]
dp[i][j] = tu[i][j] + dp[i + 1][j];
else
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) + tu[i][j];//数可能来自右边或者下方
if (dp[i][j] > c)
dp[i][j] = c;//超出了就为c
if (dp[i][j] <= 0)
dp[i][j] = -114514;//人死了先令他为负
}
//左下
for (int i = x; i <= n; i++)//从上来(因为目的地在N)
for (int j = y; j > 0; j--)//右来
{
if (i == x && j == y)
continue;
else if (i == x)
dp[i][j] = tu[i][j] + dp[i][j + 1];
else if (j == y)
dp[i][j] = tu[i][j] + dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]) + tu[i][j];//书来自右方或上方
if (dp[i][j] > c)
dp[i][j] = c;
if (dp[i][j] <= 0)
dp[i][j] = -114514;
}
//忧伤
for (int i = x; i > 0; i--)//下方来的
for (int j = y; j <= m; j++)//左方来的
{
if (i == x && j == y)
continue;
else if (i == x)
dp[i][j] = tu[i][j] + dp[i][j - 1];
else if (j == y)
dp[i][j] = tu[i][j] + dp[i + 1][j];
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) + tu[i][j];
if (dp[i][j] > c)
dp[i][j] = c;
if (dp[i][j] <= 0)
dp[i][j] = -114514;
}
//游侠
for (int i = x; i <= n; i++)//上方来的
for (int j = y; j <= m > 0; j++)
{
if (i == x && j == y)
continue;
else if (i == x)
dp[i][j] = tu[i][j] + dp[i][j - 1];
else if (j == y)
dp[i][j] = tu[i][j] + dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + tu[i][j];
if (dp[i][j] > c)
dp[i][j] = c;
if (dp[i][j] <= 0)
dp[i][j] = -114514;
}
int ans = max(max(dp[1][1], dp[1][m]), max(dp[n][1], dp[n][m]));//找出最大值
if (ans <= 0)
{
cout << "-1" << endl;
}
else
{
cout << ans << endl;
}
return 0;
}
感觉好难啊,,,,,,
在方向上似乎很容易出错呢