K Turns Allowed

Posted: 28 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja has been given the dimensions of a matrix, count the number of paths to reach the bottom right from top left with maximum k turns allowed.

A valid turn :

There are two possible scenarios when a turn can occur at point (i, j):

Turns Right: (i - 1, j)  ->  (i, j)  ->  (i, j + 1)

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains three space-separated integers ‘N’, ’M’, and ‘K’ denoting the number of rows, columns, and maximum turn around respectively.
Output Format:
For each case, we need to print the total number of possible paths % (10 ^ 9 + 7).
Note:
The answer should be in the mod(10 ^ 9 + 7)

The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100

Time limit: 1 sec.
Approach 1

Here, we will use basic recursion to calculate the number of the unique paths with ‘K’ most turns around. We can declare a function having 4 parameters as ith row index, jth row index, remaining k turns possible from that index(K), and the direction of the movement (d). For row, we consider ‘d’ equal to ‘0’ and, for column ‘d’ is equal to ‘1’. Using the recursive function we shall call the function for both adjacent cells (right cell and bottom cell), and add them up and return to the parent function. Inside our recursive function, firstly we need to have certain base conditions.

Our base conditions will into the following constraints:

  • If our current row index and column index becomes negative, we can return 0 as failure
  • If we reach the final bottom right point, we will return 1 as success.
  • If ‘K’ is equal to zero indicating no further turns:
    • If we are in the last row and our current direction is 0, then we can return 1 as a success
    • If we are in the last column and our current direction is 1, then we can return 1 as a success
    • Otherwise, we can return zero as a failure.

Now we can compute for both the directions separately looking into the current movement pattern and return to the parent function.

For each arithmetic operation, we need to use the mod ( 10 ^ 9 + 7). 

 

Algorithm:

 

  • From the main function, call the recursive function (‘countPath’) for the adjacent cells as ‘countPath(N - 2, M - 1, K, 1)’ and ‘countPath(N - 1, M - 2, K, 0)’, sum them up and return to the main function.
  • In our recursive function, we have 4 parameters as ‘i-th’ row index, ‘j-th’ row index, ‘k-th’ turn possible, and direction of movement (‘d’).
  • If our current row index and column index becomes invalid, we can return 0 as a failure.
  • If we reach the final bottom right point, we will return 1 as success.
  • If ‘K’ is equal to zero indicating no further turns:
    • If we are in the last row and our current direction is 0, then we can return 1 as a success
    • If we are in the last column and our current direction is 1, then we can return 1 as a success
    • Otherwise, we can return zero as a failure.
  • If our current direction is 0,
    • Return the summation of ‘countPath( ‘i’, ‘j’ - 1, ‘k’, ‘d’)’ + ‘countPath( ‘i’ - 1, ‘j’, ‘k’ - 1, ‘d’ ^ 1)’
  • Otherwise, our current direction is 1,
    • Return the summation of ‘countPath( ‘i’ - 1, ‘j’, ‘k’, ‘d’)’ + ‘countPath( ‘i’, ‘j’ - 1, ‘k’ - 1, ‘d’ ^ 1)’.
  •  
Try Problem