[Description]
感谢哈利波特在十月找到了不朽的魔法石，难道我们不该告诉你那仅仅是个游戏么？哇！现在哈利波特有一个真的在线任务。给你一个有R行C列的网格S，每个小格子要么有一个需要去打败的匈牙利树蜂龙，要么是他的老师斯内普离开他时留下的一瓶魔法药水。有龙的格子(i, j)需要花费|S[i][j]|的力量点，而有魔法药水的格子(i, j)可以恢复哈利波特|S[i][j]|的力量。如果哈利波特的力量在任何时候掉到了0或更少，那么他就死了，无论什么魔法石也救不了他。
哈利波特从左上角的格子(1, 1)出发，要到达右下角(R, C)。对于每个格子(i, j)，哈利波特可以选择向右到(i, j+1)或者向下到(i+1, j)，但是不能走出这整个格子S的边框。在走之前哈利波特用莫法探测清楚了每个格子里有什么，但是他不知道如何用最小力量花费来收集魔法石，所以请再一次帮助他。
[Input]
第一行一个数T，表示T组数据。
对于每组数据，第一行两个整数R和C。接下来R行，每行C个整数。从上到下是1~R行，从左到右是1~C列。若S[i][j] < 0则(i, j)包含龙，否则包含魔法石。
[Output]
对于每组数据输出一行，想要能从(1, 1)走到(R, C)，哈利波特需要在(1, 1)拥有的最小力量值。
[Sample Input]
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0
[Sample Output]
2
1
2
一开始，我是想直接一遍广搜过去，但是发现这样无法满足题目的要求，于是我们就可以二分开始的分数，然后二分检验。检验可以用ＤＰ，也可以用广搜，我用的是广搜。不过，好像听黄ｄａｌａｏ说，可以直接倒着搜一遍，不过我没有试过。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define il inline #define db double using namespace std; il int gi() { int x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*y; } il ll gl() { ll x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*y; } int n,m; int map[545][545]; int mo[545][545]; int t[1000045][2]; bool vis[545][545]; int dist[3]= {0,1,0}; il bool bfs(int x) { memset(mo,0,sizeof(mo)); memset(vis,0,sizeof(vis)); int head=0,tail=1; t[0][0]=1; t[0][1]=1; mo[1][1]=x; while(head!=tail) { int a=t[head][0],b=t[head++][1],c=mo[a][b]; vis[a][b]=0; for(int i=0; i<2; i++) { int x=a+dist[i],y=b+dist[i+1]; if (x&&y&&x<=n&&y<=m) { if (c+map[x][y]>mo[x][y]) { mo[x][y]=c+map[x][y]; if (vis[x][y]==0) { vis[x][y]=1; if (x==n&&y==m) return 1; t[tail][0]=x; t[tail++][1]=y; } } } } return 0; } } int ans; il void hzr() { int l=1,r=200000000; while(l<=r) { int m=(l+r)>>1; if(bfs(m)) ans=m,r=m-1; else l=m+1; } } int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); int s=gi(); while(s--) { ans=2e8; memset(map,0,sizeof(map)); n=gi(),m=gi(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) map[i][j]=gi(); hzr(); printf("%d ",ans); } return 0; }