7-9 treasure hunt route

7-9 Treasure hunt route

In a m That's ok n Column lattice matrix , In each square, there are treasures of different values （ Value can be positive or negative ）, What makes Xiao Ming curious is , Of all possible routes from the upper left corner to the lower right corner , What is the maximum total value of the treasure you can find ？ And this route to the maximum
How many more ？【 Be careful ： You can only go down or right from one grid to the adjacent grid , And the grid baby will be picked up .】

Input format :
The first line is an integer m,n（ No more than 100）, There will be one at the beginning of the next line m That's ok n An integer matrix of columns , Corresponding to the baby value in the square matrix （ The absolute values of these values do not exceed 500）.

Output format :
Output on a single line 2 It's an integer , They are the maximum value of the total value of the treasure that can be found and the number of routes that reach the maximum value ,2 An integer separated by a space .

sample input :
Here's a set of inputs . for example ：

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

sample output :
The corresponding output is ：

26 3

Code ：

#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 3、 ... and