hdu 2391

直接遍歷

[cpp]  #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; 
}