K Turns Allowed

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)’.
•  

In our brute force approach, we can add memorizations and improve the time complexity. We can declare a global matrix having 4 dimensions as the 4 parameters of our recursive function. Now, in this approach, when we reach a certain cell, we will check whether the output for that cell is present in the DP table or not. If the output is present for that cell, we will return that without computing for that cell again, otherwise we will compute for the cell and store the result in the DP table for further use.

• Here, DP(‘i’,’j’,’k’,1) represents we are currently on the node ( ‘i’, ’j’) with ‘k’ turns remaining and the direction is downward movement. Similarly, for DP( ‘i’, ’j’, ’k’, 0), it represents we are currently on the node ( ‘i’, ’j’) with ‘k’ turns remaining and the direction is rightward movement.

Our transitions are as follows:

• During a right turn, from (‘ i’ - 1, ‘j’)  ->  ( ‘i’, ‘j’)  ->  ( ‘i’, ‘j’ + 1), our DP table change from DP( ‘i’ - 1, ’j’, ’k’, 1) to DP( ‘i’, ’j’, ’k’, 1) to DP( ‘i’, ’j’ + 1, ’k’ - 1, 0) indicating a right turn.
• During a left turn, from ( ‘i’, ‘j’ - 1)  ->  ( ‘i’, ‘j’)  ->  ( ‘i’ + 1, ‘j’), our DP table change from DP( ‘i’, ’j’ - 1, ’k’, 0) to DP( ‘i’, ’j’, ’k’, 1) to DP( ‘i’ + 1, ’j’, ’k’ - 1, 1) indicating a right turn.

Algorithm:

• Declare a global matrix having 4 dimensions representing a number of rows and column, ‘k-th’ turn possible from the current index and current direction of movement.
• 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 that are the same as the dimension of the matrix.
• 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 the current location is already computed, we shall pick up the value from the DP table and return it.
• If our current direction is 0,
  • Update the DP table with the summation of ‘countPath( ‘i’, ‘j’ - 1, ‘k’, ‘d’)’ + ‘countPath( ‘i’ - 1, ‘j’, ‘k’ - 1, ‘d’ ^ 1)’ and return to the parent function.
• Otherwise, our current direction is 1,
  • Update the DP table with the summation of ‘countPath( ‘i’ - 1, ‘j’, ‘k’, ‘d’)’ + ‘countPath( ‘i’, ‘j’ - 1, ‘k’ - 1, ‘d’ ^ 1)’ and return to the parent function.