ZSTU2545-地道战源码

#include
#include
#include
using namespace std;
int main(void)
{
    int n,m,i,j,k,g,dp[120][120],x[120][120],y[120][120];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,100000,sizeof(dp));
        memset(x,100000,sizeof(x));
        memset(y,100000,sizeof(y));
        for(i=1;i<=n;i++)
           for(j=1;j<=m-1;j++)
              scanf("%d",&x[i][j]);
        for(i=1;i<=m;i++)
           for(j=1;j<=n-1;j++)
              scanf("%d",&y[j][i]);
        for(i=1;i<=n;i++)
           for(j=1;j<=m;j++)
              dp[i][j]=0;
        g=n>m?n:m;
        for(i=2;i<=g;i++)
        {
            k=i+1;
            for(j=i;j>=1;j--)
                dp[j][k-j]=min((dp[j][k-j-1]+x[j][k-j-1]),(dp[j-1][k-j]+y[j-1][k-j]));
        }
        for(i=2;i<=g;i++)
        {
            k=i+g;
            for(j=i;j<=g;j++)
               dp[k-j][j]=min((dp[k-j][j-1]+x[k-j][j-1]),(dp[k-j-1][j]+y[k-j-1][j]));
        }
        printf("%d\n",dp[n][m]);
    }   
    return 0;
}