Ways to reach the bottom-right corner of a matrix with exactly k turns allowed

Given a M x N matrix, count number of different ways to reach the bottom-right corner of a matrix from its top-left corner with exactly K turns allowed and using only the directions right or down.


 

A turn is defined as a down move immediately followed by a right move or a right move immediately followed by a down move.

For example, consider a 3 x 3 matrix

 
3x3 matrix


Input: k = 1
Output: Total number of paths are 2

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2)

 
Input: k = 2
Output: Total number of paths are 2

(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)

 
Input: k = 3
Output: Total number of paths are 2

(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)

Input: k = 4
Output: Total number of paths are 0

 

 
We can recursively solve this problem. The idea is to keep track of the current direction and number of turns so far. Now if the current direction is along column, then we have two options for the next move: we continue moving along column or we turn right and decrement number of turns by 1. Similarity, if the current direction is along row, we can continue moving in same direction or we can turn down and decrement number of turns by 1. A path is found if destination is reached with exactly K turns.

 

Download   Run Code

Output:

Total number of paths is 4

 
The time complexity of above solution is exponential since it re-computes the same sub-problems again and again. We can easily optimize the code to run in O(M*N*k) time with Dynamic Programming. The idea is to store the results of function calls and return the cached result when the same input occurs again.

 
Exercise:

1. Implement dynamic programming solution using memoization.
2. Modify the solution for at-most K turns.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of