POJ 2498 Martian Mining (二)
ude
#include
#include
#include
#define N 510
using namespace std;
int yey[N][N],blo[N][N];
int up[N][N],Left[N][N],dp[N][N];
int main()
{
//freopen("data.in","r",stdin);
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
{
break;
}
memset(Left,0,sizeof(Left));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&yey[i][j]);
Left[i][j] = Left[i][j-1] + yey[i][j];
}
}
memset(up,0,sizeof(up));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&blo[i][j]);
up[i][j] = up[i-1][j] + blo[i][j];
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int k = max(dp[i][j-1]+up[i][j],dp[i-1][j]+Left[i][j]);
k = max(k,dp[i-1][j-1]+Left[i][j-1]+up[i-1][j]+max(yey[i][j],blo[i][j]));
dp[i][j] = max(k,dp[i][j]);
}
}
printf("%d\n",dp[n][m]);
}
return 0;
}