计蒜客习题：逃生

---

问题描述

蒜头君在玩一款逃生的游戏。在一个 n×m 的矩形地图上，蒜头位于其中一个点。地图上每个格子有加血的药剂，和掉血的火焰，药剂的药效不同，火焰的大小也不同，每个格子上有一个数字，如果格子上的数字是正数说明是一个药剂代表增加的生命值，如果是负数说明是火焰代表失去的生命值。
蒜头初始化有 v 点血量，他的血量上限是 c，任何时刻他的生命值都不能大于血量上限，如果血量为 0则会死亡，不能继续游戏。
矩形地图上的四个角(1,1)，(1,m)，(n,1)，(n,m)为游戏的出口。游戏中只要选定了一个出口，就必须朝着这个方向走。例如，选择了左下的出口，就只能往左和下两个方向前进，选择了右上的出口，就只能往右和上两个方向前进，左上和右下方向的出口同理。
如果成功逃生，那么剩余生命值越高，则游戏分数越高。为了能拿到最高分，请你帮忙计算如果成功逃生最多能剩余多少血量，如果不能逃生输出−1。
输入格式
第一行依次输入整数 n，m，x，y，v，c（1

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int dp[1020][1020][4];
int G[1020][1020];
int main() {
  memset(dp, 0, sizeof(dp));
  int m, n, x, y, v, c;
  cin >> n >> m >> x >> y >> v >> c;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> G[i][j];
    }
    G[x][y]=v;
  }
  dp[x][y][0]=v;
  dp[x][y][1]=v;
  dp[x][y][2]=v;
  dp[x][y][3]=v; 
  // dp0--->(1,1)
  for (int i = x; i > 0; i--) {
    for (int j = y; j > 0; j--) {
      if (i == x && j == y)
        continue;
      else if (i == x)dp[i][j][0] = dp[i][j+1][0]+G[i][j];
      else if (j == y)dp[i][j][0] = dp[i + 1][j][0] + G[i][j];
      else
        dp[i][j][0] = max(dp[i][j + 1][0], dp[i + 1][j][0]) + G[i][j];
      if (dp[i][j][0] >= c)
        dp[i][j][0] = c;
      if (dp[i][j][0] <= 0)
        dp[i][j] [0]= -0x3f3f3f3f;
    }
  }
  // dp1--->>(1,m)
    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][1] = dp[i][j-1][1]+G[i][j];
      else if (j == y)
        dp[i][j][1] = dp[i + 1][j][1] + G[i][j];
      else
        dp[i][j][1] = max(dp[i][j - 1][1], dp[i + 1][j][1]) + G[i][j];
      if (dp[i][j][1] >= c)
        dp[i][j][1] = c;
      if (dp[i][j][1] <= 0)
        dp[i][j] [1]= -0x3f3f3f3f;
    }
    }
    //dp2--->n,1
    for (int i = x; i <=n; i++) {
    for (int j = y; j > 0; j--) {
      if (i == x && j == y)
        continue;
      else if (i == x)dp[i][j][2] = dp[i][j+1][2]+G[i][j];
      else if (j == y)
        dp[i][j][2] = dp[i - 1][j][2] + G[i][j];
      else
        dp[i][j][2] = max(dp[i][j + 1][2], dp[i - 1][j][2]) + G[i][j];
      if (dp[i][j][2] >= c)
        dp[i][j][2] = c;
      if (dp[i][j][2] <= 0)
        dp[i][j] [2]= -0x3f3f3f3f;
    }
    }
    //dp3--->n,m
    for (int i = x; i <=n; i++){
    for (int j = y; j <=m; j++) {
      if (i == x && j == y)
        continue;
      else if (i == x)dp[i][j][3] = dp[i][j-1][3]+G[i][j];
      else if (j == y)
        dp[i][j][3] = dp[i - 1][j][3] + G[i][j];
      else
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i - 1][j][3]) + G[i][j];
      if (dp[i][j][3] >= c)
        dp[i][j][3] = c;
      if (dp[i][j][3] <= 0)
        dp[i][j] [3]= -0x3f3f3f3f;
    }
      }
      int ans = max(dp[1][1][0], dp[1][m][1]);
      int anss = max(dp[n][m][3], dp[n][1][2]);
      int ansss=max(ans, anss);
      if(ansss<=0)cout<<"-1";
      else cout<<ansss; 
      return 0;
}