Matrix Gym - Coding Question

Ninja has put on some extra weight during lockdown. He has decided to join a gym to shed this extra weight off. He joined the Matrix Gym, where the trainer has planned an elaborate exercise for him. It is upto Ninja to decide how many calories he wants to burn during his workout, whereas the trainer designs the exercise. The basic idea of each day remains the same. Ninja has to perform his exercise by crossing his Matrix Gym, which is a 2-D Grid consisting of hurdle cells (represented by “ # ”) and clear cells (represented by “ . “ ). He has to avoid the hurdles, and by entering each clear cell he burns 5 calories. He begins from the top-left corner of the grid. It is given that starting position has no hurdle. He has to reach the bottom-right cell which is also hurdle free. You have to find out if a path exists through which Ninja can burn his decided amount of calories. Ninja can take only one step at a time. Also, when Ninja is standing at (i, j), he can move to (i, j+1) and (i+1, j) only (right and bottom cells). If such a path is possible, print “Yes”, otherwise print “No”. If more than one path is present in the gym through which the calories can be burnt, find the path which burns the maximum calories, and print the extra amount of calories burnt by Ninja.

Input Format:

The first line of input contains an integer N which denotes the number of rows in the grid. 
The following line of input contains N space separated strings deciding the structure of hurdle and clear cells in the grid
The third line contains the number of calories to be burnt.

Constraints:

1 <= N <= 10^5
1 <= calories <= 10^5

Output Format:

For each query, you have to print “Yes” along with additional calories burnt (if any) if the path is found, otherwise you have to print “No”.

Sample Input 1:

3
..## #.## #...
15

Sample Output 1:

Yes 10

Explanation:

For the given input the grid formed is [ ‘..##’ , ‘#.##’ , ‘#...’ ]
For this grid, Ninja can easily travel from cell (0,0) which is his starting point, till cell (2,3) which is his end point, and burn 25 calories in the process.
He had decided to burn 15 calories. Hence additional calories burnt are 25-15 = 10

Sample Input 2:

4
...## .#..# .##.# ..#..
30

Sample Output 2:

Yes 5

Explanation:

For the given input the grid formed is [ ‘...##’ , ‘.#..#’ , ‘.##.#’ , ‘..#..’ ]. 
For this grid, Ninja can easily travel from cell (0,0) which is his starting point, till cell (3,4) which is his end point, and burn 25 calories in the process.
He had decided to burn 15 calories. Hence additional calories burnt are 35-30 = 5

Sample Input 3:

4
...## .#..# .##.# ..#..
35

Sample Output 3:

Yes 

Explanation:

For the given input the grid formed is [ ‘...##’ , ‘.#..#’ , ‘.##.#’ , ‘..#..’ ]
For this grid, Ninja can easily travel from cell (0,0) which is his starting point, till cell (3,4) which is his end point, and burn 25 calories in the process.
He had decided to burn 15 calories. Hence additional calories burnt are 35-35 = 0 

from sys import stdin

2

​

3

# Main

4

​

5

n = int(stdin.readline().strip())

6

# String array

7

arr = [x for x in input().split()]

8

calories = int(stdin.readline().strip())

9

INT_MIN = -2**31

10

​

11

cols = len(arr[0])

12

dp = [[INT_MIN for j in range(cols + 1)] for i in range(n + 1)]

13

​

14

for i in range(n):

15

    for j in range(cols):

16

        if arr[i][j] == '.' :

17

            dp[i][j] = 0

18

​

19

​

20

for i in range(n - 1, -1, -1):

21

    for j in range(cols - 1, -1, -1):

22

        if(i == n-1 and  j == cols-1):

23

            continue

24

        elif(arr[i][j] == '.'):

25

            dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + 5

26

​

27

​

28

if(dp[0][0] < calories):

29

    print("No")

30

else:

31

    if dp[0][0] == calories:

32

        print("Yes")

33

    else:

34

        print("Yes", dp[0][0] - calories)

35

​