学步园

直接遍历

#include<stdio.h>
#include<string.h>
int map[1010][1010],dp[1010][1010];
int main()
{
	int i,j,n,m,t,op=1;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				scanf("%d",&map[i][j]);
			memset(dp,0,sizeof(dp));
			dp[0][0]=map[0][0];
			for(i=0;i<n;i++)
				for(j=0;j<m;j++)
				{
					if(i-1>=0&&dp[i][j]<map[i][j]+dp[i-1][j])
						dp[i][j]=map[i][j]+dp[i-1][j];
					if(j-1>=0&&dp[i][j]<map[i][j]+dp[i][j-1])
						dp[i][j]=map[i][j]+dp[i][j-1];
					if(i-1>=0&&j-1>=0&&dp[i][j]<map[i][j]+dp[i-1][j-1])
						dp[i][j]=map[i][j]+dp[i-1][j-1];
				}
				printf("Scenario #%d:\n",op++);
				printf("%d\n\n",dp[n-1][m-1]);
	}
	return 0;
}