7-9 寻宝路线

7-9 寻宝路线

在一个m行n列方格矩阵中，每一个方格内摆放着价值不等的宝贝（价值可正可负），让小明感到好奇的是，从左上角到达右下角的所有可能路线中，能捡到宝贝的价值总和最大是多少？而且这种达到最大值的路线
又有多少条？【注意：只能从一个格子向下或向右走到相邻格子，并且走到的格子宝贝一定会被捡起。】

输入格式:
第一行为整数m，n（均不大于100），下一行开始会有一个m行n列的整数方阵，对应方格矩阵中的宝贝价值（这些值的绝对值都不超过500）。

输出格式:
单独一行输出2个整数，分别为能捡到宝贝价值总和的最大值和达到最大值的路线数量，2个整数间隔一个空格。

输入样例:
在这里给出一组输入。例如：

4 5
2 -1 6 -2 9
-3 2 5 -5 1
5 8 3 -2 4
5 2 8 -4 7

输出样例:
对应的输出为：

26 3

代码：

#include <stdio.h>
#include <stdlib.h>
int m,n;
int a[110][110];
int times[110][110];
int rem[110][110];
find(x,y)
{
    
    if(x==1&&y==1)
        return 0;
    else
    {
    
        if(x==1)
        {
    
            times[x][y]+=times[x][y-1];
            return rem[x][y-1];
        }
        else if(y==1)
        {
    
            times[x][y]=times[x-1][y];
            return rem[x-1][y];
        }
        else
        {
    
            if(rem[x-1][y]>rem[x][y-1])
            {
    
                times[x][y]+=times[x-1][y];
                return rem[x-1][y];
            }
            else if(rem[x-1][y]<rem[x][y-1])
            {
    
                times[x][y]+=times[x][y-1];
                return rem[x][y-1];
            }
            else
            {
    
                times[x][y]+=times[x-1][y]+times[x][y-1];
                return rem[x][y-1];
            }
        }
    }
}
int main()
{
    
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    times[1][1]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            rem[i][j]=find(i,j)+a[i][j];
    printf("%d %d",rem[m][n],times[m][n]);
    return 0;
}

202206222109三