计蒜客：逃生

逃生

Description

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

小信初始化有 v 点血量，他的血量上限是 c，任何时刻他的生命值都不能大于血量上限，如果血量为 0 则会死亡，不能继续游戏。

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

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

Input

第一行依次输入整数 n，m，x，y，v，c（1<n,m≤1000，1≤x≤n，1≤y≤m，1≤v≤c≤10000）, 其中 n,m 代表地图大小，(x,y) 代表小信的初始位置，v 代表小信的初始化血量，c 代表小信的生命值上限。

接下来 n 行，每行有 m 个数字，代表地图信息。（每个数字的绝对值不大于100，地图中小信的初始位置的值一定为 0）

Output

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

Sample Input 1 

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

Sample Output 1

10

由于有四个出口：左上、左下、右上、右下，所以我们可以将到达每个出口的最大值算出来，再求出所有出口的最大值就可以了。

#include<iostream>
using namespace std;
const int inf = 679488;
const int maxn = 1000 + 5;

int maze[maxn][maxn];
int health[maxn][maxn];
int n, m, x, y, v, c;

void run(int act){
	switch(act){
		case 1:{//左上角
			for(int i = x - 1; i >= 1; i--){
				for(int j = y - 1; j >= 1; j--){
					int tmp1 = health[i + 1][j] + maze[i][j];
					int tmp2 = health[i][j + 1] + maze[i][j];
					health[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
					if(health[i][j] > c) health[i][j] = c;
                  	if(health[i][j] <= 0) health[i][j] = -inf;
				}
			}
			break;
		}case 2:{//左下角
			for(int i = x + 1; i <=n; i++){
				for(int j = y - 1; j >= 1; j--){
					int tmp1 = health[i - 1][j] + maze[i][j];
					int tmp2 = health[i][j + 1] + maze[i][j];
					health[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
					if(health[i][j] > c) health[i][j] = c;
                  	if(health[i][j] <= 0) health[i][j] = -inf;
				}
			}
			break;
		}//右上角
		case 3:{//
			for(int i = x - 1; i >= 1; i--){
				for(int j = y + 1; j <= m; j++){
					int tmp1 = health[i + 1][j] + maze[i][j];
					int tmp2 = health[i][j - 1] + maze[i][j];
					health[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
					if(health[i][j] > c) health[i][j] = c;
                  	if(health[i][j] <= 0) health[i][j] = -inf;
				}
			}
			break;
		}
		case 4:{//右下角
			for(int i = x + 1; i <= n; i++){
				for(int j = y + 1; j <= m; j++){
					int tmp1 = health[i - 1][j] + maze[i][j];
					int tmp2 = health[i][j - 1] + maze[i][j];
					health[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
					if(health[i][j] > c) health[i][j] = c;
                  	if(health[i][j] <= 0) health[i][j] = -inf;
				}
			}
			break;
		}
	}
}

int main(){
	cin >> n >> m >> x >> y >> v >> c;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> maze[i][j];
		}
	}
	
	health[x][y] = v;
	for(int i = x - 1; i >= 1; i--){
		health[i][y] = health[i + 1][y] + maze[i][y];
	}
	for(int i = x + 1; i <= n; i++){
		health[i][y] = health[i - 1][y] + maze[i][y];
	}
	for(int i = y - 1; i >= 1; i--){
		health[x][i] = health[x][i + 1] + maze[x][i];
	}
	for(int i = y + 1; i <= m; i++){
		health[x][i] = health[x][i - 1] + maze[x][i];
	}//现将起点所在的十字初始化
	
	for(int i = 1; i <= 4; i++){
		run(i);//每个终点都运算一次
	}
	
	int mmax = -inf;
	if(health[1][1] > mmax){
		mmax = health[1][1];
	}
	if(health[1][m] > mmax){
		mmax = health[1][m];
	}
	if(health[n][1] > mmax){
		mmax = health[n][1];
	}
	if(health[n][m] > mmax){
		mmax = health[n][m];
	}

	if(mmax <= 0) cout << -1;
	else if(mmax > c) cout << c;
	else cout << mmax;
	return 0;
}