Grid problem - Urgent

Super Mario wants to save the princess but this time the tasks are not easy. So he asked you to help him so he can save her.

Mario is in a Castle. The castle is made of a N*M grid. Currently Mario is at position (x1,y1) and he wants to save the princess who is at (x2,y2) and then they want to exit the grid. The exit door of the grid is at (N,M).Initially Mario's health is H units.

Mario can move from one cell to any 4 adjacent cells. But he cannot move to a cell if DRAGON lives there. If a adjacent room is occupied by a LION then he can go there by sacrificing his life by K units. If the cell is empty then he can go there easily without any loss of life.

You have to tell Mario if he can save the princess and then exit the grid given that his life should remain greater than zero when he exits the grid.


Code reuired for the same, I have many approaches including Dfs, dynamic programming but nothing works


If it is possible, you have to print Mario's remaining health when he exited. If there are many ways, print the maximum remaining health at exit door among all possible ways.

If it is not possible, Print "Sorry Mario" (Without Quotes)

You don’t have to worry about princess's health assume that she has infinite health. :D

If once a lion is killed by Mario then when Mario moves to some other cell the Lion becomes alive again. (After all its a Magical Lion)

Please use Fast I/O

Input Format

First line of input contains two integer N , M , H , K. (No. of Rows,No. of cols., Initial health of Mario , Amount of health he loses while fighting with one Lion)

Next N line contains M characters each. if A[i][j]=='D' then Dragon lives there if A[i][j]=='L' then Lion lives there if A[i][j]=='F' then that place is empty. Next line contains x1,y1,x2,y2 where (x1,y1) is Initial place of Mario and (x2,y2) is place of princess.

It is guaranteed that Mario's initial position would be empty.

Constraints

1 <= N*M <=4000000

1 <= H , K <= 1000000000

1 <= X1,X2 <= N

1 <= Y1,Y2 <= M

Output Format

If it is possible, you have to print Mario's remaining health when he exited. If there are many ways, print the maximum remaining health at exit door among all possible ways.

If it is not possible , Print "Sorry Mario" (Without Quotes).

Sample Input 0

2 3 10 5
FDF
FLF
1 1 2 1

Sample Output 0

5
Last edited on
What have you tried?
This sounds cool but what are you expecting from us on here?
What have you tried so far?
Is there anything you don't understand how to do?
Guess it's not that urgent.
¯\_(ツ)_/¯
Topic archived. No new replies allowed.