 New update is available. Click here to update.
Topics

# K Turns Allowed

Moderate 0/80
Average time to solve is 25m   +1 more companies

## Problem statement

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)
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100

Time limit: 1 sec.
``````
Sample Input 1:
``````1
3 3 2
``````
Sample Output 1:
``````4
``````
Explanation of Sample Input 1:
``````Test case 1:
For the first test case of sample output 1, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 2 ways
Hence our answer shall be 4
``````
Sample Input 2:
``````2
4 5 3
2 3 4
``````
Sample Output 2:
``````19
3
``````
Explanation of Sample Input 2:
``````Test case 1:
For the first test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 5 ways
3 turns -> 12 ways
Hence our answer shall be 19

Test case 2:
For the second test case of sample output 2, we can reach the right bottom point through the following ways:
0 turns -> 0 ways
1 turn -> 2 ways
2 turns -> 1 ways
Hence our answer shall be 3.
`````` Console