Walls and Gates – find shortest escape paths

You are given a m x n 2D grid initialized with these three possible values.

-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF

After running your function, the 2D grid should be:

3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

We know that there are some gates to escape. First we can find all the positions of the gate (val=0) and then we do back track to all possible empty spaces (val=INF) and update the value of the empty space cells to the minimum distance to the nearest gate. We can do this using a simple BFS and update the paths accordingly similar to we do in Dijkstra shortest path problem keeping the invariant room[i][j] <= room[r][c]+1 where room[i][j] is a neighbor empty space and room[r][c] is current position of a node on a path to escape. Important part is to know where the walls are and prune the search tree from the position we discover a wall ahead (val=-1).

Below is the implementation in O(n) time and O(n) space of this idea using BFS.

	//find exit path to the door
	public static void findExitWallsAndGates(int room[][]){
		Queue<Pair> queue = new LinkedList<Pair>();
		int n = room.length;
		int m = room[0].length;
		//down, right, up, left
		Pair[] dirs = {new Pair(1, 0), new Pair(0, 1), new Pair(-1, 0), new Pair(0, -1)};
		
		for(int i=0; i<room.length; i++){
			for(int j=0;j<room[0].length; j++){
				if(room[i][j] == 0){
					queue.offer(new Pair(i, j));
				}
			}
		}
		
		//BFS search
		while(!queue.isEmpty()){
			Pair pos = queue.poll();
			int r = pos.first;
			int c = pos.second;
			
			for(Pair dir : dirs){
				int i = r+dir.first;
				int j = c+dir.second;
				
				//prune the tree
				if(i < 0 || j < 0 || i>=n || j >= m || room[i][j] <= room[r][c]+1){
					continue;
				}
				
				room[i][j] = room[r][c]+1;
				queue.offer(new Pair(i, j));
			}
		}
	}