I attended Amazon interview last month. I was asked this question with a followup. I was able to answer the first one, but couldn't answer the followup. I still don't know how to do it.

First question:

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. I was able to solve this with plain BFS.

Followup:

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 

Again the goal is to escape fire. I was suggested to use backtracking, however I didn't know how to do it for the entire matrix. Can someone please help me with solving this?