Найдите недостающую логику в динамическом программировании, реализованную в моем коде, чтобы найти количество путей, имеющих максимальную сумму.

---

Я написал динамическое программирование для функции maxcountPath, чтобы найти количество путей, имеющих максимальную сумму.Но получал неверный вывод

----------------------входной------------------

3
6
e 9 6 1 5 5
2 4 9 3 x 1
6 2 8 x 4 5
7 9 7 1 1 1
2 3 5 4 4 4
4 4 3 9 8 s
9
e 4 x 9 1 7 5 9 1
2 9 8 2 9 6 x 8 8
9 5 9 5 7 1 x 2 1
2 3 8 9 x 3 8 7 8
8 8 9 2 x 2 7 8 2
4 6 2 6 8 7 9 5 9
x 6 3 8 8 3 5 8 7
9 5 7 3 5 8 4 8 1
x 4 4 5 8 7 4 1 s
7
e 2 8 7 6 7 4
2 6 6 2 x 6 7
3 1 1 4 x 7 2
1 4 2 6 1 7 6
x 7 8 9 x 4 x
7 1 1 4 x 2 4
8 6 5 9 1 1 s

----------------Ожидаемые результаты---------------------

65 1
101 15
60 1

Что я уже пробовал:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char a[100][100];
int i,j,n,max_path_sum,val,max_path_count;

int isvalidate(int i, int j,int c)
{
    if(i >= 0 && i < n && j>=0 && j<n && c>=0 && c <= max_path_sum)
        return 1;
    else 
        return 0;
    
}
  
int max(int a,int b, int c)
{
     if(a >= b && a >= c)
         return a;
     else if(b >= a && b >= c)
         return b;
     else 
         return c;
}

int maxcountPath(int n, int c)
{
    int countDP[n][n];
    memset(countDP, 0, sizeof(countDP));
    
    countDP[0][0] = c;
    
    for(i = 1; i < n; i++)
    {
        if(a[i][0] != 'x')
        {
            countDP[i][0] = countDP[i-1][0] - (a[i][0]-'0');
        }
        else
            break;
    }
    
    for(i = 1 ; i < n; i++)
    {
        if(a[0][i] != 'x')
        {
            countDP[0][i] = countDP[0][i-1] - (a[0][i]-'0');
        }
        else
            break;
    }
    
    
    
    for(i = 1; i < n; i++)
    {
        for(j = 1; j < n; j++)
        {       
                if(a[i][j] != 'x')
                {   
                    val = a[i][j]-'0';
                    countDP[i][j] = (countDP[i-1][j]-val)-(countDP[i][j-1]-val)-(countDP[i-1][j-1]-val);
                }
                else
                    continue;
        }
        
    }
    
        return countDP[n-1][n-1];

}

int maxsumPath(char a[][100], int n)
{   
    int maxpathDP[n][n];
    
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            maxpathDP[i][j] = 0;
        }
    }
    
    for(i = 1; i < n; i++)
    {
        if(a[i][0] != 'x')
            maxpathDP[i][0] = a[i][0]-'0' +maxpathDP[i-1][0];
        else
            break;
    
    }
    
    for(j = 1; j < n; j++)
    {
        if(a[0][j] != 'x')
            maxpathDP[0][j] = a[0][j]-'0'+maxpathDP[0][j-1];
        else
            break;
    }
    
    for(i = 1; i < n; i++)
    {
        for(j = 1; j < n; j++)
        {
            if(a[i][j] == 'x')
            {    
                continue;
            }
            else
            {
                if(a[i][j] == 's')
                {   
                    maxpathDP[i][j] = max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]); 
                }
                else
                {
                 
                    maxpathDP[i][j] = a[i][j]-'0' + max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]);
                }
            }
        }
    }
    
   return maxpathDP[n-1][n-1];
    
}
 
int main()
{   
    int t;
    scanf("%d", &t);

    while(t--)
    {   
        scanf("%d", &n);
      
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                scanf(" %c", &a[i][j]);
            }
        }
        
        max_path_sum = maxsumPath(a,n);
        
        a[0][0] = '0';
        a[n-1][n-1] = '0';
        
        max_path_count = maxcountPath(n,max_path_sum);
        
        if(max_path_count == 0)
		{
            max_path_sum = 0;
        }
         printf("%d %d\n",max_path_sum,max_path_count);
    }
    
    return 0;
}

---