Count number of paths with k turns - GeeksforGeeks
Given three numbers m, n and k where m and n represent number of rows and columns respectively in a grid. Count number of paths to reach bottom right from top left with maximum k turns allowed.
What is a turn? A movement is considered turn, if we were moving along row and now move along column. OR we were moving along column and now move along row.
Read full article from Count number of paths with k turns - GeeksforGeeks
Given three numbers m, n and k where m and n represent number of rows and columns respectively in a grid. Count number of paths to reach bottom right from top left with maximum k turns allowed.
What is a turn? A movement is considered turn, if we were moving along row and now move along column. OR we were moving along column and now move along row.
There are two possible scenarios when a turn can occur at point (i, j): Turns Right: (i-1, j) -> (i, j) -> (i, j+1) Down Right Turns Down: (i, j-1) -> (i, j) -> (i+1, j) Right Down
Examples:
Input: m = 3, n = 3, k = 2 Output: 4 See below diagram for four paths with maximum 2 turns. Input: m = 3, n = 3, k = 1 Output: 2
countPaths(i, j, k): Count of paths to reach (i,j) from (0, 0) countPathsDir(i, j, k, 0): Count of paths if we reach (i, j) along row. countPathsDir(i, j, k, 1): Count of paths if we reach (i, j) along column. The fourth parameter in countPathsDir() indicates direction. Value of countPaths() can be written as: countPaths(i, j, k) = countPathsDir(i, j, k, 0) + countPathsDir(i, j, k, 1) And value of countPathsDir() can be recursively defined as: // Base cases // If current direction is along row If (d == 0) // Count paths for two cases // 1) We reach here through previous row. // 2) We reach here through previous column, so number of // turns k reduce by 1. countPathsDir(i, j, k, d) = countPathsUtil(i, j-1, k, d) + countPathsUtil(i-1, j, k-1, !d); // If current direction is along column Else // Similar to above countPathsDir(i, j, k, d) = countPathsUtil(i-1, j, k, d) + countPathsUtil(i, j-1, k-1, !d);
We can solve this problem in Polynomial Time using Dynamic Programming. The idea is to use a 4 dimensional table dp[m][n][k][d] where m is number of rows, n is number of columns, k is number of allowed turns and d is direction.
Time complexity of above solution is O(m*n*k)
// table to store to store results of subproblems
int
dp[MAX][MAX][MAX][2];
// Returns count of paths to reach (i, j) from (0, 0)
// using at-most k turns. d is current direction
// d = 0 indicates along row, d = 1 indicates along
// column.
int
countPathsUtil(
int
i,
int
j,
int
k,
int
d)
{
// If invalid row or column indexes
if
(i < 0 || j < 0)
return
0;
// If current cell is top left itself
if
(i == 0 && j == 0)
return
1;
// If 0 turns left
if
(k == 0)
{
// If direction is row, then we can reach here
// only if direction is row and row is 0.
if
(d == 0 && i == 0)
return
1;
// If direction is column, then we can reach here
// only if direction is column and column is 0.
if
(d == 1 && j == 0)
return
1;
return
0;
}
// If this subproblem is already evaluated
if
(dp[i][j][k][d] != -1)
return
dp[i][j][k][d];
// If current direction is row, then count paths for two cases
// 1) We reach here through previous row.
// 2) We reach here through previous column, so number of
// turns k reduce by 1.
if
(d == 0)
return
dp[i][j][k][d] = countPathsUtil(i, j-1, k, d) +
countPathsUtil(i-1, j, k-1, !d);
// Similar to above if direction is column
return
dp[i][j][k][d] = countPathsUtil(i-1, j, k, d) +
countPathsUtil(i, j-1, k-1, !d);
}
// This function mainly initializes 'dp' array as -1 and calls
// countPathsUtil()
int
countPaths(
int
i,
int
j,
int
k)
{
// If (0, 0) is target itself
if
(i == 0 && j == 0)
return
1;
// Initialize 'dp' array
memset
(dp, -1,
sizeof
dp);
// Recur for two cases: moving along row and along column
return
countPathsUtil(i-1, j, k, 1) +
// Moving along row
countPathsUtil(i, j-1, k, 0);
// Moving along column
}