欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计蒜客 逃生dp

程序员文章站 2022-07-12 09:10:39
...

 

题目:

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

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

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

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

输入格式

第一行依次输入整数 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 代表蒜头的生命值上限。

接下来 nnn 行,每行有 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<bits/stdc++.h>
using namespace std;
int n,m,x,y,v,c;
int val[1010][1010]={{0}};
int dp[1010][1010]={{0}};
int mixx=-0x3f3f3f3f;
void solve(){//左上
	for(int i=x;i>=1;i--){
		for(int j=y;j>=1;j--){
			if(i==x&&j==y){
				dp[x][y]=v;
				continue;
			}
			else if(i==x){
				dp[i][j]=dp[i][j+1]+val[i][j];
				if(dp[i][j]<=0){
					dp[i][j]=mixx;
				}
				if(dp[i][j]>c){
					dp[i][j]=c;
				}
			}
			else if(j==y){
				dp[i][j]=dp[i+1][j]+val[i][j];
				if(dp[i][j]<=0){
					dp[i][j]=mixx;//1即为死亡区域 
				}
				if(dp[i][j]>c){
					dp[i][j]=c;
				}
			}
			else if(j<y){
				dp[i][j]=max(dp[i+1][j]+val[i][j],dp[i][j+1]+val[i][j]);
				if(dp[i][j]<=0){
				   dp[i][j]=mixx;
				}
				if(dp[i][j]>c){
					dp[i][j]=c;
				}
				}
	 }
}
//右上 
	 for(int i=x;i>=1;i--){
		for(int j=y+1;j<=m;j++){
			if(i==x){
				dp[i][j]=dp[i][j-1]+val[i][j];
				if(dp[i][j]<=0)
				{
					dp[i][j]=mixx;//1即为死亡区域 
				}
				if(dp[i][j]>c)
				{
					dp[i][j]=c;
				}
			}
			else if(j>y)
			{
				dp[i][j]=max(dp[i+1][j]+val[i][j],dp[i][j-1]+val[i][j]);
				if(dp[i][j]<=0)
				{
					dp[i][j]=mixx;
				}
				if(dp[i][j]>c)
				{
					dp[i][j]=c;
				}
				}
			}
	 } 
//左下
	for(int i=x+1;i<=n;i++){
		for(int j=y;j>=1;j--){
			if(j==y){
			    dp[i][j]=dp[i-1][j]+val[i][j];
				if(dp[i][j]<=0){
					dp[i][j]=mixx;//1即为死亡区域 
				}
				if(dp[i][j]>c){
					dp[i][j]=c;
				}
			}
			else if(j<y)
			{
			     dp[i][j]=max(dp[i-1][j]+val[i][j],dp[i][j+1]+val[i][j]);
			     if(dp[i][j]<=0)
			     {
					dp[i][j]=mixx;
				}
				if(dp[i][j]>c)
				{
					dp[i][j]=c;
				}
				}
			}
		}
//右下 
	for(int i=x+1;i<=n;i++){
		for(int j=y+1;j<=m;j++){
			if(j>y){
			    dp[i][j]=max(dp[i-1][j]+val[i][j],dp[i][j-1]+val[i][j]);
				if(dp[i][j]<=0){
					dp[i][j]=mixx;
					}
				if(dp[i][j]>c){
					dp[i][j]=c;
				}
				}
			}
		}
	 	int t=max(dp[1][1],dp[1][m]);
	 	t=max(t,dp[n][1]);
	 	t=max(t,dp[n][m]);
	 	if(t>0){
	 		printf("%d\n",t);
	 	    return;
	    }	  
	 else{
	 	cout<<"-1"<<endl;
	 	return ;
	 }
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&v,&c);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&val[i][j]);
		}
	}
	solve();
	return 0;
	
}