'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

K Turns Allowed

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
9 upvotes
Asked in companies
SalesforceAmazonZepto

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.
Full screen
Console