New update is available. Click here to update.

Topics

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

```
1 <= T <= 5
1 <= N <= 50
1 <= M <= 50
1 <= K <= 100
Time limit: 1 sec.
```

```
1
3 3 2
```

```
4
```

```
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
```

```
2
4 5 3
2 3 4
```

```
19
3
```

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