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)); } } }