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

Tips

• 这里附上了BFS和DFS的解法，但是显然BFS更快。最先找到gate，然后以gate为root进行BFS遍历，叶子节点为四个方向。
• 最巧妙地部分是这里定义了static final d，来确定四个方向的位置，即通过用i，j +/- 1的方式来得到[i, j+1],[i+1,j],[i, j-1], [i-1, j]。
• 注意在遍历四个方向时不要出界。 *

Code:

``````public class Solution {
// use this d we can get the pos of the four room adjacent to x
public static final int[] d = {0, 1, 0, -1, 0};

public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0 || rooms.length == 0) {
return;
}
Deque<Integer> queue = new ArrayDeque<>();
// put the gate into the queue
for (int i = 0; i < rooms.length; ++i) {
for (int j = 0; j < rooms.length; ++j) {
if (rooms[i][j] == 0) {
}
}
}

while (!queue.isEmpty()) {
int x = queue.remove();
//define the position of the gate
//i is the row index and j is the col index
int i = x / rooms.length, j = x % rooms.length;
for (int k = 0; k < 4; ++k) {
int m = i + d[k], n = j + d[k + 1];

// keep the room inside the border and if it's empty, put the distance
if (m >= 0 && m < rooms.length && n >= 0 && n < rooms.length && rooms[m][n] == Integer.MAX_VALUE) {
rooms[m][n] = rooms[i][j] + 1;
}
}
}
}
}
``````

``````private static int[] d = {0, 1, 0, -1, 0};

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) dfs(rooms, i, j);
}

public void dfs(int[][] rooms, int i, int j) {
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1];
if (0<= p && p < rooms.length && 0<= q && q < rooms.length && rooms[p][q] > rooms[i][j] + 1) {
rooms[p][q] = rooms[i][j] + 1;
dfs(rooms, p, q);
}
}
}
``````