计蒜客 逃生（基础动态规划）

蒜头君在玩一款逃生的游戏。在一个 n \times mn×m 的矩形地图上，蒜头位于其中一个点。地图上每个格子有加血的药剂，和掉血的火焰，药剂的药效不同，火焰的大小也不同，每个格子上有一个数字，如果格子上的数字是正数说明是一个药剂代表增加的生命值，如果是负数说明是火焰代表失去的生命值。

蒜头初始化有 vv 点血量，他的血量上限是 cc，任何时刻他的生命值都不能大于血量上限，如果血量为 00 则会死亡，不能继续游戏。

矩形地图上的四个角(1, 1)(1,1)，(1, m)(1,m)，(n, 1)(n,1)，(n, m)(n,m)为游戏的出口。游戏中只要选定了一个出口，就必须朝着这个方向走。例如，选择了左下的出口，就只能往左和下两个方向前进，选择了右上的出口，就只能往右和上两个方向前进，左上和右下方向的出口同理。

如果成功逃生，那么剩余生命值越高，则游戏分数越高。为了能拿到最高分，请你帮忙计算如果成功逃生最多能剩余多少血量，如果不能逃生输出 -1−1。

输入格式

第一行依次输入整数 nn，mm，xx，yy，vv，cc（1 < n,m \leq 10001<n,m≤1000，1 \leq x \leq n1≤x≤n，1 \leq y \leq m1≤y≤m，1 \leq v \leq c \leq 100001≤v≤c≤10000）, 其中 n, mn,m 代表地图大小，(x, y)(x,y) 代表蒜头君的初始位置，vv 代表蒜头的初始化血量，cc代表蒜头的生命值上限。

接下来 nn 行，每行有 mm 个数字，代表地图信息。（每个数字的绝对值不大于100100，地图中蒜头君的初始位置的值一定为 00）

输出格式

一行输出一个数字，代表成功逃生最多剩余的血量，如果失败输出 -1−1。

样例输入

4 4 3 2 5 10
1 2 3 4
-1 -2 -3 -4
4 0 2 1
-4 -3 -2 -1

样例输出

10

思路: 将4中出口的结果都存起来  取最大值即可 每一种解法利用动态规划求解

注意.1、如果同行同列 代表起点  跳过 不进行处理 

2、若与起点同行或者与起点同列  则到达该点的方式只有一种

3、若某点的值大于给定最大值  则应重置该点的值 如小于0 则赋给一个很小的数字 （以防加其他项变正 出现错解）

状态转移方程   tmp[i][j]=max("可以到达该点的两种方式的较大值")+该点的值;

ac代码:

#include <bits/stdc++.h>
#include <vector>
#include <memory.h>

using namespace std;

int n,m,x,y,v,c,dp[1010][1010],tmp[1010][1010];

int main()

{
	
	vector<int> a;
	
	cin>>n>>m>>x>>y>>v>>c;
	
	for(int i=1;i<=n;i++) 
	
	{
		
		for(int j=1;j<=m;j++)
		
		cin>>dp[i][j];
	}
	
	// 左上
	
	memset(tmp,0,sizeof(tmp)); 
	
	tmp[x][y]=v;
	
	for(int i=x;i>=1;i--)
	
	{
		
		for(int j=y;j>=1;j--)
		
		{
			
			if(i==x&&j==y)//代表该点是起始点  跳过
			
			continue;
			
			else if(i==x)//代表同一行
			
				tmp[i][j]=tmp[i][j+1]+dp[i][j];//代表从右侧走到该点
			
			else if(j==y)//代表同一列  只能从下面到该点
			
				tmp[i][j]=tmp[i+1][j]+dp[i][j]; 
			
			else
			
				tmp[i][j]=max(tmp[i+1][j],tmp[i][j+1])+dp[i][j];
				
			if(tmp[i][j]>c)
			
			tmp[i][j]=c;
			
			if(tmp[i][j]<0)
			
			tmp[i][j]=-100000;
		}
	}
	
	a.push_back(tmp[1][1]);
	
	//右上
	
	 memset(tmp,0,sizeof(tmp));
	 
	 tmp[x][y]=v;
	 
	 for(int i=x;i>=1;i--)
	 
	 {
	 	
	 	for(int j=y;j<=m;j++)
	 	
	 	{
	 		
	 		if(i==x&&j==y)
	 		
	 		continue;
	 		
	 		else if(i==x)//代表同一行 只能从其左侧过来 
			 
			tmp[i][j]=tmp[i][j-1]+dp[i][j];
			
			else if(j==y)//代表同一列  只能从其下面上来
			
			tmp[i][j]=tmp[i+1][j]+dp[i][j];
			
			else
			
			tmp[i][j]=max(tmp[i+1][j],tmp[i][j-1])+dp[i][j];
			
			if(tmp[i][j]>c)
			
			tmp[i][j]=c; 
			
			if(tmp[i][j]<0)
			
			tmp[i][j]=-100000;
		}
	 }
	
	a.push_back(tmp[1][m]);
	
	//左下
	
	memset(tmp,0,sizeof(tmp)); 
	
	tmp[x][y]=v;
	
	for(int i=x;i<=n;i++)
	
	{
		
		for(int j=y;j>=1;j--)
		
		{
			
			if(i==x&&j==y)
			
			continue;
			
			else if(i==x)//同一行  只能从右边过来 
			
			tmp[i][j]=tmp[i][j+1]+dp[i][j];
			
			else if(j==y)//同一列 只能从上面下来
			
			tmp[i][j]=tmp[i-1][j]+dp[i][j];
			
			else
			
			tmp[i][j]=max(tmp[i][j+1],tmp[i-1][j])+dp[i][j];
			
			if(tmp[i][j]>c)
			
			tmp[i][j]=c;
			
			if(tmp[i][j]<0)
			
			tmp[i][j]=-100000; 
		}
	}
	
	a.push_back(tmp[n][1]);
	
	//右下 
	
	memset(tmp,0,sizeof(tmp));
	
	tmp[x][y]=v;
	
	for(int i=x;i<=n;i++)
	
	{
		
		for(int j=y;j<=m;j++)
		
		{
			
			if(i==x&&j==y)
			
			continue;
			
			else if(i==x)
			
			tmp[i][j]=tmp[i][j-1]+dp[i][j];
			
			else if(j==y)
			
			tmp[i][j]=tmp[i-1][j]+dp[i][j];
			
			else
			
			tmp[i][j]=max(tmp[i][j-1],tmp[i-1][j])+dp[i][j];
			
			if(tmp[i][j]>c)
			
			tmp[i][j]=c;
			
			if(tmp[i][j]<0)
			
			tmp[i][j]=-100000;
		}
	}
	
	a.push_back(tmp[n][m]);
	
	sort(a.begin(),a.end());
	
	if(a[3]>=0)
	
	cout<<a[3];
	
	else
	
	cout<<-1;
	
	return 0;
}