Bob wants to play game named Easter Diablo Maze. The game is set in a R x C grid having wall and ghosts which replicate every second, touching ghost kills the droid. The score of the game is determined by the number of seconds the droid survives Rules of the game are as follows:
Each cell in the grid is empty or contains wall.
Some cell contains ghosts, they multiply after every second to all of its adjacent empty cells (cell that share an edge are called adjacent)
droid and ghost cannot jump a wall.
droid is free to move to it's adjacent empty cells
Game ends when ghost fills the droid's cell.
Return the maximum time that the droid survives in the game or -1 if droid can survive indefinitely
If the cell value(val):
1.) val = 1 — cell contain wall
2.) val = 0 — cell is empty
3.) val = 3 — initial location of Droid
4.) val = 5 — location of Ghost
Constraints: 1<= R <=100 and 1<= C <=100
Example — 1:
3 3
5 0 0
0 3 0
0 0 0
Ans: 4
Example — 2:
5 5
5 0 0 1 0
0 5 0 1 0
0 0 0 1 0
1 1 1 0 0
0 0 0 3 0
Ans: -1
