[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;
else
dp[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;
}