Problem Description
度度熊是一僅僅喜歡探險的熊。一次偶然落進了一個m*n矩陣的迷宮。該迷宮僅僅能從矩陣左上角第一個方格開始走。僅僅有走到右上角的第一個格子才算走出迷宮，每一次僅僅能走一格，且僅僅能向上向下向右走曾經沒有走過的格子，每個格子中都有一些金币（或正或負，有可能遇到強盜攔路搶劫，度度熊身上金币能夠為負，須要給強盜寫欠條），度度熊剛開始時身上金币數為0，問度度熊走出迷宮時候身上最多有多少金币？
Input
輸入的第一行是一個整數T（T< 200），表示共同擁有T組資料。
每組資料的第一行輸入兩個正整數m，n（m<=100，n<=100）。接下來的m行。每行n個整數，分别代表對應格子中能得到金币的數量，每一個整數都大于等于-100且小于等于100。
Output
對于每組資料，首先須要輸出單獨一行”Case #?
:”，當中問号處應填入目前的資料組數，組數從1開始計算。
每組測試資料輸出一行，輸出一個整數。代表依據最優的打法。你走到右上角時能夠獲得的最大金币數目。
Sample Input
2
3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90
2 2
1 1
1 1
Sample Output
Case #1:
18
Case #2:
4
對于一個點能夠從三個方向到達，從上，從左，從下。
由于一個點不能走多次，我們能夠得到一個非常easy的結論。假設從上到達這個點，那麼之後我們就僅僅能向下，或者向右走了。從下到達類似。
僅僅有從左到達，三個方向都能夠走。
這裡dp[i][j][k]表示x,y這個點從k這個方向過來的最大值。當中k=0,1,2.0表示從左邊到達該點，1表示從上面到達該點，2表示從以下到達該點。
依據以上結論，能夠得到一個非常easy的狀态轉移方程：
dp[i][j+1][0] = max(,dp[i][j][0],dp[i][j][1],dp[i][j][2])+ graph[i][j+1];
dp[i+1][j][1] =max(dp[i][j][0],dp[i][j][1]) + graph[i+1][j];
dp[i-1][j][2] =max(dp[i][j][0],dp[i][j][2]) + graph[i-1][j];
由以上轉移方程非常easy得到。我們能夠對每一列，先從上到向下更新該點向下走所到達點的值，再從下到上更新該點向上和向右分别到達點的值。
最後的答案就是從左到達和從以下到達右上方的點的最大值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-8
#define MAX 100010
#define INF 99999999
#define MOD 1000000007
#define mem(a) memset(a,-1,sizeof(a))
#define mem1(a) memset(a,0,sizeof(a))
#define zero(x) ( x > +eps ) - ( x < -eps )
using namespace std;
struct NODE
{
int x ,y;
int dir;
};
int dp[110][110][3];
int n ,m;
int graph[110][110];
int main()
{
int t;
scanf("%d",&t);
for(int r = 1;r <= t;r++)
{
printf("Case #%d:\n",r);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
scanf("%d",&graph[i][j]);
}
}
for(int i = 0;i <= n +1;i++)
{
for(int j = 0;j <= m + 1;j++)
{
dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -INF;
}
}
dp[1][1][1] = dp[1][1][0] = graph[1][1];
for(int i = 1;i <= n;i++)
{
dp[i][2][0] = max(dp[i][1][0],dp[i][1][1]) + graph[i][2];
dp[i+1][1][1] = max(dp[i][1][0],dp[i][1][1]) + graph[i+1][1];
}
for(int i = 2;i <= m;i++)
{
for(int j = 1;j < n;j++)
{
dp[j+1][i][1] = max(dp[j][i][1],dp[j][i][0]) + graph[j+1][i];
}
for(int j = n;j >= 1;j--)
{
dp[j-1][i][2] = max(dp[j][i][2],dp[j][i][0]) + graph[j-1][i];
dp[j][i+1][0] = max(dp[j][i][0],max(dp[j][i][1],dp[j][i][2])) + graph[j][i+1];
}
}
printf("%d\n",max(dp[1][m][0],dp[1][m][2]));
}
return 0;
}