Description
Given a room represented like a grid, you have to escape from the fire. The grid looks like the following where 0 represents empty place you can move through, 1 represents you (a person) and 2 represents fire.
You can consider yourself escaped if you reach any of the sides that's not on fire (ie., grid[i][j]!=2 && i = 0 || j == 0 || i == m-1 || j == n-1 where 0<=i<m , 0 <=j<n and m,n being length and height of the grid).
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0
Goal is to find the shortest distance from 1 to any of the sides.
Followup question:
Now for every step you take, the fire grows a step in all four directions. For the example above, for the next step you make, the room would look like this.
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0
2 2 2 0 0 0 0 0 0 0 2 0 0 0 2 2 2 0
0 2 0 0 0 0 0 0 0 2 2 2 0 0 0 2 0 0
0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0
0 2 2 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0
0 0 2 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0