Labyrinth

23 41 -1 1 02 -2 4 23 5 1 -902 21 11 1 Sample Output
Case #1:18Case #2:4 Source2014年百度之星程序设计大赛 - 资格赛
#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int INF = 0x3f3f3f3f;int a[110][110],dp[110][110][3];int max(int a,int b){    return a>b? a:b;}int main(){    int t;    cin>>t;    for(int Case=1;Case<=t;++Case)    {        int n, m;        cin>>m>>n;        memset (dp, -INF, sizeof(dp));        for(int i=1;i<=m;++i)            for(int j=1;j<=n;++j)            {                cin>>a[i][j];            }        dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=a[1][1];        for(int i=2;i<=m;++i)            dp[i][1][0]=dp[i-1][1][0]+a[i][1];        for(int j=2;j<=n;++j)        {            for (int i=1;i<=m;++i)            {                dp[i][j][2]=max(dp[i][j-1][0],max(dp[i][j-1][1],dp[i][j-1][2]))+a[i][j];            }            for(int i=2;i<=m;++i)            {                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][2])+a[i][j];            }            for(int i=m-1;i>=1;--i)            {                dp[i][j][1]=max(dp[i+1][j][2],dp[i+1][j][1])+a[i][j];            }        }        int ans =max(dp[1][n][0],max(dp[1][n][1],dp[1][n][2]));        cout<<"Case #"<<Case<<":/n";        cout<<ans<<endl;    }    return 0;}