-
[1673] 迷宫问题
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
Alex的猫咪不小心走进了迷宫，Alex为了心爱的猫咪，决定进入迷宫去解救他的猫咪。
已知猫咪坐标为(n - 1, m - 1)，Alex坐标为(0, 0)，Alex只能往下或者往右走，且不能走出迷宫，迷宫的大小为n＊m，迷宫每个格子上都有一个数字x，如果x大于0，说明Alex走到这个格子上后，血量增加x；反之血量减少x，要求不论在哪个格子，血量都至少大于等于1，且血量没有上限，问，如果Alex要成功从(0,0)走到(n - 1, m - 1)，需要的初始血量最少应该是多少？
- 输入
- 先输入 T，说明有T组数据。
接下来T个case
每个case上
输入 n， m（迷宫的大小）（1 <= n, m <= 1000）
接下来输入迷宫，保证每格都是整型。
且每个数字绝对值都小于等于100 - 输出
- 输出Alex 最小需要的初始血量值。
- 样例输入
-
2 3 3 2 -1 1 -1 0 -1 -1 -1 3 3 3 3 -9 7 -3 -2 -8 0 -1 0
- 样例输出
-
1 2
题目链接：NBUT 1673
当时周赛那会儿说是DP题……某聚聚几下就A了（膜一下Orz），然而我连学长讲解也没听懂，时隔N个月又回来撸了一发，发现用学长那个DP做不来…………，然后自己在纸上对样例推了下就过了，就是if-else有点多= =……
学长代码好像是逆着推的，我写的是正着推，用结构体记录从起始点到当前点的最低所需血量least和当前最多留下的血now；
先特判起始点，然后对每一个邻接的点都进行判断，选出最低所需血量least最小的前驱点赋值给当前点，然后更新now，看now够不够消耗，够的话就只更新now，不够的话还要把least更新，然后就差不多了。
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1010;
int pos[N][N];
struct info
{int least;int now;
};
info dp[N][N];
int main(void)
{int tcase,i,j,n,m;scanf("%d",&tcase);while (tcase--){scanf("%d%d",&n,&m);for (i=0; i<n; ++i){for (j=0; j<m; ++j)scanf("%d",&pos[i][j]);}if(pos[0][0]>=0)dp[0][0].least=1;elsedp[0][0].least=-pos[0][0]+1;dp[0][0].now=dp[0][0].least+pos[0][0];for (i=0; i<n; ++i){for (j=0; j<m; ++j){if(!i&&!j)continue;if(!i){dp[i][j]=dp[i][j-1];if(dp[i][j-1].now+pos[i][j]>=1) dp[i][j].now+=pos[i][j];else{int dx=-pos[i][j]+1-dp[i][j-1].now;dp[i][j].least+=dx;dp[i][j].now=1;}}else if(!j){dp[i][j]=dp[i-1][j];if(dp[i-1][j].now+pos[i][j]>=1) dp[i][j].now+=pos[i][j];else{int dx=-pos[i][j]+1-dp[i-1][j].now;dp[i][j].least+=dx;dp[i][j].now=1;}}else{info a=dp[i-1][j],b=dp[i][j-1];if(a.now+pos[i][j]>=1)a.now+=pos[i][j];else{int dx=-pos[i][j]+1-a.now;a.least+=dx;a.now=1;}if(b.now+pos[i][j]>=1)b.now+=pos[i][j];else{int dx=-pos[i][j]+1-b.now;b.least+=dx;b.now=1;}dp[i][j]=a.least<b.least?a:b;}}}printf("%d\n",dp[n-1][m-1].least);}return 0;
}
