很水的dp,状态转移方程告诉了
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int maze[1100][1100],dp[1100][1100]; int dir[3][2]={{-1,0},{0,-1},{-1,-1}}; int r,c; bool inline IN(int x,int y) { if(1<=x&&x<=c&&1<=y&&y<=r) return true; else return false; } int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%d %d",&r,&c); for(int j=1;j<=r;j++) for(int k=1;k<=c;k++) scanf("%d",&maze[j][k]); memset(dp,0,sizeof(dp)); dp[1][1]=maze[1][1]; int max=-1,tx,ty; for(int j=1;j<=r;j++) for(int k=1;k<=c;k++) { max=-1; for(int p=0;p<3;p++) { tx=j+dir[p][0]; ty=k+dir[p][1]; if(IN(tx,ty)&&dp[tx][ty]>max) max=dp[tx][ty]; } if(max!=-1) dp[j][k]=max+maze[j][k]; } /*for(int j=1;j<=r;j++) { for(int k=1;k<=c;k++) printf("%d* ",maze[j][k]); printf("\n"); }*/ /* for(int j=1;j<=r;j++) { for(int k=1;k<=c;k++) printf("%d ",dp[j][k]); printf("\n"); }*/ printf("Scenario #%d:\n%d\n\n",i,dp[r][c]); } system("pause"); return 0; }