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*.

For example, consider a 3 x 3 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> using namespace std; // M x N matrix #define M 3 #define N 3 // Function to check whether (i, j) is valid matrix coordinate or not bool isValid(int i, int j) { return (i >= 0 && i < M && j >= 0 && j < N); } // Recursive function to count number of different ways to reach the last // cell (M-1,N-1) of a matrix from the given cell (i,j) with k turns left. // isCol flag is true when current direction is along column; false otherwise int totalWays(int i, int j, int k, bool isCol) { // if number of turns are exhausted or if the cell is invalid if (k == -1 || !isValid(i, j)) { return 0; } // if destination is reached with exactly k turns if (k == 0 && i == M - 1 && j == N - 1) { return 1; } // if the current direction is along column if (isCol) { // 1. continue moving along column // 2. turn right and decrement number of turns by 1 return totalWays(i + 1, j, k, isCol) + totalWays(i, j + 1, k - 1, !isCol); } // if the current direction is along row // 1. continue moving along row // 2. turn down and decrement number of turns by 1 return totalWays(i, j + 1, k, isCol) + totalWays(i + 1, j, k - 1, !isCol); } // Function to count number of different ways to reach the bottom-right corner // of a matrix from its top-left corner with exactly k turns allowed. int totalWays(int i, int j, int k) { return totalWays(i + 1, j, k, true) + // Recur by moving along column totalWays(i, j + 1, k, false); // Recur by moving along row } // main function int main() { int k = 2; cout << "Total number of ways is " << totalWays(0, 0, k); return 0; } |

`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