Как найти количество путей в матрице, имеющей максимальную сумму от верхнего левого угла до нижнего правого угла с препятствиями " x " на ней

Patrice T

Какой результат вы получаете и какого результата ожидаете ?

Diaesh Antony

----ВХОД-----
5
15
e 1 1 7 x 7 6 8 4 2 2 7 3 4 8
5 2 3 x 2 5 2 3 8 x 8 2 x 8 1
6 3 1 x 2 9 9 4 7 x 9 8 1 8 6
8 1 x x 9 x 8 6 3 5 2 x 4 9 4
5 5 3 5 5 9 x 3 8 9 3 1 1 x 5
3 6 1 1 x x 2 3 x 3 7 9 4 9 2
6 9 1 8 x x 5 3 2 1 2 9 x 7 x
4 1 x 1 8 1 2 9 6 5 6 1 1 х 2
x 6 4 3 9 2 5 x 7 x 2 8 6 x x
8 6 x x 7 1 3 8 x 5 3 x x 6 7
4 5 6 5 6 1 9 x 3 4 2 2 2 2 8
x 7 5 2 2 8 x x 4 5 3 5 8 x 1
9 5 9 5 x 4 8 3 x x 5 6 1 2 6
1 4 x x x x 4 3 2 1 5 8 2 x 4
6 5 2 7 4 6 4 7 3 x 4 8 x 7 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 с
7
е 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 с
7
е 5 4 9 9 3 7
x 3 1 4 5 7 5
3 6 3 x 6 x 5
7 1 5 8 x 9 1
8 4 3 9 6 8 3
2 x x 5 9 3 7
3 2 6 4 7 4 с
3
е 6 1
4 8 9
9 9 с
----------ВЫХОД-------------------
143 ?
101 15
60 1
65 3
23 2

Patrice T

Совет: покажите достаточно кода, чтобы мы могли его запустить.

Diaesh Antony

#включить <stdio.h>
#include <string.h>
#include <stdlib.h>

char a[100][100];
инт я,J,Н,max_path_sum,max_path_count;

isvalidate типа int(тип int я, инт Дж,тип int в C)
{
если(я и gt;= 0 &&усилителя; я &Л; П &амп;&амп; Дж&ГТ;=0 &амп;&амп; Дж&ЛТ;п &ампер;&ампер;="" с=""&ГТ;=0 &&усилителя; г &ЛТ;= max_path_sum)
возврат 1;
еще
возвращает 0;

}

инт максимум(в инт,инт б, инт с)
{
Если(а &ГТ;= б &амп;&амп; в &ГТ;= с)
вернуть;
остальное, если(B &ГТ;= &ампер;&ампер; б &ГТ;= с)
вернуться б;
еще
возвращение с;
}
/* Подход к запоминанию для нахождения количества путей, имеющих максимальную сумму */

maxcountPath типа int(тип int я,инт Дж,тип int в C)
{
int countDP[n][n][max_path_sum];

если(i==0 & & amp; j==0 && c== 0)
{
если (((a[i][j]-'0') - c) ==0)
return countDP[i][j][c] = 1;
еще
return countDP[i][j][c] = 0;
}

если(я==0 &&усилителя; isvalidate(я,J,C) и усилитель;& а[я][Дж] != 'х')
вернуться countDP[я][Дж][с] = maxcountPath(я,J-1,С-(а[я][Дж]-'0'));

остальное, если(с j==0 &&усилителя; isvalidate(я,J,C) и усилитель;& а[я][Дж] != 'х')
вернуться countDP[я][Дж][с] = maxcountPath(я-1,J В,С-(а[я][Дж]-'0'));

остальное, если(isvalidate(я,J,к.))
вернуться countDP[я][Дж][с] = maxcountPath(я,J-1,С-(а[я][Дж]-'0')) +
maxcountPath(я-1,J В,С-(а[я][Дж]-'0')) + maxcountPath(я-1,j-1,и С-(а[я][Дж]-'0'));
еще
return countDP[i][j][c] = 0;

}
/* Подход DP для нахождения пути максимальной суммы от верхнего левого угла до нижнего правого угла */

int maxsumPath(char a[][100], int n)
{
int maxpathDP[n][n];

для(i = 0; i < n; i++)
{
для(j = 0; j < n; j++)
{
maxpathDP[i][j] = 0;
}
}

для(i = 1; i < n; i++)
{
если(a[i][0] != 'x')
maxpathDP[i][0] = a[i][0]-'0' +maxpathDP[i-1][0];
еще
перерыв;

}

для(j = 1; j < n; j++)
{
если(a[0][j] != 'x')
maxpathDP[0][Дж] = а[0][Дж]-'0'+maxpathDP[0][j-1 в];
еще
перерыв;
}

для(i = 1; i < n; i++)
{
для(j = 1; j < n; j++)
{
если(a[i][j] == 'x')
{
продолжить;
}
еще
{
если(a[i][j] == 's')
{
maxpathDP[i][j] = max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]);
}
еще
{

maxpathDP[i][j] = a[i][j]-'0' + max(maxpathDP[i-1][j-1],maxpathDP[i-1][j],maxpathDP[i][j-1]);
}
}
}
}

возврат maxpathDP[n-1][n-1];

}

тап_п()
{
int t;
scanf("%d", &t);

while(t--)
{
scanf("%d", &n);

для (i = 0; i < n; i++)
{
для (j = 0; j < n; j++)
{
scanf(" %c", &a[i][j]);
}
}

max_path_sum = maxsumPath(а,н);

а[0][0] = '0';
a[n-1][n-1] = '0';

max_path_count = maxcountPath(n-1,n-1,max_path_sum);

if(max_path_count == 0)
{
max_path_sum = 0;
}
printf("%d %d\n",max_path_sum,max_path_count);
}

возвращает 0;
}

CPallini

Пожалуйста, напишите точный код. Эта линия

if(i >= 0 && i < n && j>=0 && j<n &&="" c="">=0 && c <= max_path_sum)