数字矩阵

冷不防 2022-07-13 13:11 195阅读 0赞

#### Problem Description ####

bLue 站在了一个 n\*m 的填有数字的矩阵中，他可以选择从矩阵的四个顶点之一出发，到达斜对面的顶点。每一步必须向靠近目的地的方向移动，且每次移动都可以累加所在位置上的数字。

例如，bLue 选择从左上角出发，那么目的地为右下角，则他每次只能向右或向下移动一格。

现在他想知道在所有的走法中，能获得的最大累加和是多少。你能帮助他吗？

#### Input ####

输入数据有多组（数据组数不超过 50），到 EOF 结束。

对于每组数据：

*  第 1 行输入 2 个整数 n, m (1 <= n, m <= 100)，表示矩阵的行数和列数。
 *  接下来 n 行，每行包含 m 个用空格隔开的整数 aij (0 <= aij <= 10000)，表示这个数字矩阵。

#### Output ####

对于每组数据，输出 1 行，包含 1 个整数，表示 bLue 能获得的最大的累加和。

#### Example Input ####

3 4
    1 2 3 4
    1 0 6 5
    4 7 2 0

#### Example Output ####

#include<stdio.h>
    #include<string.h>
    int a[102][102];
    int sum[102][102];
    int max (int a, int b, int c)
    {
        int max_abc;
        max_abc=a;
        if(b>max_abc)
            max_abc=b;
        if(c>max_abc)
            max_abc=c;
        return max_abc;
    }
    int sum1 (int n, int m)
    {
        int i,j;
        for(i=n;i>=1;i--)
        {
            for(j=1;j<=m;j++)
            {
                sum[i][j] = a[i][j]+max(sum[i][j-1], sum[i+1][j-1], sum[i+1][j]);
            }
        }
        return sum[1][m];
    }
    int sum2 (int n, int m)
    {
        int i,j;
        for(i=n;i>=1;i--)
        {
            for(j=m;j>=1;j--)
            {
                sum[i][j] = a[i][j]+max(sum[i][j+1], sum[i+1][j+1], sum[i+1][j]);
            }
        }
        return sum[1][1];
    }
    int sum3 (int n,int m)
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                sum[i][j] =a[i][j]+max(sum[i-1][j], sum[i-1][j-1], sum[i][j-1]);
            }
        }
        return sum[n][m];
    }
    int sum4 (int n,int m)
    {
        int i, j;
        for(i=1;i<=n;i++)
        {
            for(j=m;j>=1;j--)
            {
                sum[i][j] = a[i][j]+max(sum[i-1][j],sum[i-1][j+1],sum[i][j+1]);
            }
        }
        return sum[n][1];
    }
    int main()
    {
        int n,m;
        int i,j;
        int k;
        int sum_;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            memset(a,0,sizeof(a));
            memset(sum,0,sizeof(sum));
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            sum_=sum1(n,m);
            k=sum2(n,m);
            if(k>sum_)
                sum_=k;
            k=sum3(n,m);
            if(k>sum_)
                sum_=k;
            k=sum4(n,m);
            if(k>sum_)
                sum_=k;
            printf("%d\n",sum_);
        }
        return 0;
    }