286. Walls and Gates (Medium) Facebook Google
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 withINF.
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
The performances of MultiEnd is very stable and have time complexities of O(n^2) for a
n x nsquare matrix.The time complexity for NaiveBFS should be O(n^4) in the worst case. However is not shown in our tests. The performance of recursive DFS is very unstable. It is much slower than BFS if the rooms are interconnected. It is only faster than BFS when small groups of rooms are isolated. In the worst case the time complexity is also O(n^4). Thus, for this problem we should prefer BFS over DFS. And the best Solution is Multi End BFS.
Solution 1: DFS O(m * n); O(max(m, n))
Traverse the array, when find 0, start DFS to update the nearest distance from empty room to gate.
During DFS, base cases are that if the search range is out of boundary, return directly return.
If the previous distance in empty room is smaller than current distance, directly return.
Otherwise update it and start DFS from the 4 directions of current position.
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0) {
return;
}
for (int i = 0; i < rooms.length; i++) {
for (int j = 0; j < rooms[0].length; j++) {
if (rooms[i][j] == 0) { //找门而不是找空房间
dfs(rooms, i, j, 0);
}
}
}
}
private void dfs(int[][] rooms, int i, int j, int d) {
if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) {
return; //rooms[i][j] < d means i has been updated, otherwise i is the empty room.
}
rooms[i][j] = d; //update
dfs(rooms, i - 1, j, d + 1);
dfs(rooms, i + 1, j, d + 1);
dfs(rooms, i, j - 1, d + 1);
dfs(rooms, i, j + 1, d + 1);
}
Solution 2: Multi End BFS O(m * n); 最稳定
public static final int[] d = {0, 1, 0, -1, 0};
public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0) return;
int m = rooms.length, n = rooms[0].length;
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (rooms[i][j] == 0) queue.offer(i * n + j); // Put gates in the queue
while (!queue.isEmpty()) {
int x = queue.poll();
int i = x / n, j = x % n;
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1]; // empty room
if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] == Integer.MAX_VALUE) {
rooms[p][q] = rooms[i][j] + 1;
queue.offer(p * n + q);
}
}
}
}
Solution 3: naive BFS
public static final int[] d = {0, 1, 0, -1, 0};
public void wallsAndGates(int[][] rooms) {
if (rooms.length == 0) return;
for (int i = 0; i < rooms.length; ++i)
for (int j = 0; j < rooms[0].length; ++j)
if (rooms[i][j] == 0) bfs(rooms, i, j);
}
private void bfs(int[][] rooms, int i, int j) {
int m = rooms.length, n = rooms[0].length;
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(i * n + j); // Put gate in the queue
while (!queue.isEmpty()) {
int x = queue.poll();
i = x / n; j = x % n;
for (int k = 0; k < 4; ++k) {
int p = i + d[k], q = j + d[k + 1];
if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] > rooms[i][j] + 1) {
rooms[p][q] = rooms[i][j] + 1;
queue.offer(p * n + q);
}
}
}
}
Follow Up:
1.题目变了，空白的地方默认值不是INF 所以原题里不需要处理但是面试这题要处理一下