In NxN matrix containing numbers and block 'x'.find the number of path from the source 's' to destination 'd' which adds upto given sum 'k'. Use Dynamic programming to solve this.Move in down ,right and diagonal direction.
input:
--------------
k = 3
s 1 1
1 x 1
1 1 d
output = 2
--------------
k = 5
e 1 1 1
1 1 1 1
1 1 1 1
1 1 1 s
output = 20
-------------
k = 7
e 2 3
2 x 2
1 2 s
output = 1
-------------
What I have tried:
I have tried using recursion, as it will take more time complexity.
int countpath(char a[][100], int i,int j,int val)
{
if (
(
(i == n-1) &&
j == (n-1)
)
&&
(
(a[n-1][n-1] == k) ||
(a[n-2][n-2] == k) ||
(a[n-1][n-2] == k) ||
(a[n-2][n-1] == k)
)
)
{
return 1;
}
else
return 0;
a[0][0] = 0;
if (
i = 0 &&
j < n-1 &&
a[i][j+1] != 'x'
)
return countpath(a, 0, j+1, (a[i][j]+a[i][j+1])-'0');
if (
j = 0 &&
i < n-1 &&
a[i+1][j] != 'x'
)
return countpath(a, i+1, 0, (a[i][j]+a[i+1][j])-'0');
if ( a[i][j] != 'x' )
return countpath(a, i+1,j+1, (a[i+1][j+1]+a[i+1][j]+a[i][j+1])-'0');
}