# Walls and Gates

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 than 2147483647.
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
``````

``````class Coord {
int x;
int y;
public Coord(int x, int y) { this.x = x; this.y = y;}
}

int[][] delta = {{-1, 0},{1, 0},{0, 1},{0, -1}};
public void bfs(int[][] rooms, int i, int j) {
boolean[][] visited = new boolean[rooms.length][rooms.length];
Coord source = new Coord(i, j);

// Use queue to perform bfs search, if visited, mark, if is gate, mark number
int curr_distance = 1;
q.offer(source);
while(!q.isEmpty()) {
int qsize = q.size();

for(int m = 0; m < qsize; m++) {
Coord curr = q.poll();
visited[curr.x][curr.y] = true;
for(int k = 0; k < 4; k++) {
Coord c = new Coord(curr.x + delta[k], curr.y + delta[k]);

if(!(c.x < 0 || c.x >= rooms.length || c.y < 0 || c.y >= rooms.length || rooms[c.x][c.y] == -1) && !visited[c.x][c.y])
q.offer(c);
else
continue;
if(rooms[c.x][c.y] == 0) {
rooms[source.x][source.y] = curr_distance;
return;
}
}
}

curr_distance++;
}

}
public void wallsAndGates(int[][] rooms) {
for(int i = 0; i < rooms.length; i++) {
for(int j = 0; j < rooms.length; j++) {
int shortest = 0;
if(rooms[i][j] == Integer.MAX_VALUE) {
bfs(rooms, i, j);
}
}
}
}
``````

``````class Solution {
int[][] delta = {{-1, 0},{1, 0},{0, 1},{0, -1}};

public void wallsAndGates(int[][] rooms) {
for(int i = 0; i < rooms.length; i++) {
for(int j = 0; j < rooms.length; j++) {
if(rooms[i][j] == 0) {
q.offer(new int[]{i, j});
}
}
}

while(!q.isEmpty()) {
int[] curr = q.poll();
for(int i = 0; i < 4; i++) {
int[] nber = new int[]{curr + delta[i], curr + delta[i]};
if (nber < 0 || nber >= rooms.length || nber < 0 || nber >= rooms.length || rooms[nber][nber] != Integer.MAX_VALUE)
continue;
rooms[nber][nber] = rooms[curr][curr] + 1;
q.offer(nber);
}
}
}
}
``````