## 286. Walls and Gates

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

1. `-1`- A wall or an obstacle.
2. `0`- A gate.
3. `INF`- Infinity means an empty room. We use the value `2^31- 1 = 2147483647`to represent `INF`as you may assume that the distance to a gate is less than `2147483647`.

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

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
``````

Thoughts:

1. BFS and fill the empty rooms with current distance

Code: T: O(mn); S:O(mn)

``````class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms.length == 0|| rooms[0].length == 0) return;
int [] d = {0,1,0,-1,0};
for(int i = 0; i < rooms.length; i++){
for(int j =0; j< rooms[0].length; j++){
if(rooms[i][j] == 0) queue.offer(new int[]{i,j});
}
}

while(!queue.isEmpty()){
int [] pos  = queue.poll();
int row = pos[0], col = pos[1];
for(int i = 0; i < 4; i++){
int x = row + d[i];
int y = col + d[i+1];
if(x >= 0 && x < rooms.length && y>=0 && y< rooms[0].length && rooms[x][y] == Integer.MAX_VALUE){
rooms[x][y] = rooms[row][col] + 1;
queue.offer(new int[]{x,y});
}
}

}

}
}
``````