05 August 2008
一个使用这三个可能值初始化的 m x n 网格房间。
-1表示墙壁或障碍物。
0表示门。
INF Infinity 表示空房间。我们使用值 2^31 - 1 = 2147483647 来表示 INF，因为您可以假设到门的距离小于 2147483647。 用到最近门的距离填充每个空房间。如果无法到达门，则应填充 INF。
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
final int EMPTY = Integer.MAX_VALUE;
final int GATE = 0;
final int WALL = -1;
Queue<int[]> queue = new LinkedList<>();
public void wallsAndGates(int[][] rooms) {
if (rooms == null)
return;
int rows = rooms.length;
if (rows == 0) {
return;
}
int cols = rooms[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (rooms[i][j] == GATE) {
queue.add(new int[]{i, j});
}
}
}
while (!queue.isEmpty()) {
int[] pointer = queue.poll();
addToRoom(pointer[0], pointer[1], rooms, pointer[0], pointer[1] + 1);
addToRoom(pointer[0], pointer[1], rooms, pointer[0], pointer[1] - 1);
addToRoom(pointer[0], pointer[1], rooms, pointer[0] - 1, pointer[1]);
addToRoom(pointer[0], pointer[1], rooms, pointer[0] + 1, pointer[1]);
}
}
public void addToRoom(int rs, int cs, int[][] rooms, int r, int c) {
if (r < 0 || r >= rooms.length || c < 0 || c >= rooms[rs].length || rooms[r][c] != EMPTY) {
return;
}
rooms[r][c] = rooms[rs][cs] + 1;
queue.add(new int[]{r, c});
}
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
/*
https://leetcode.com/problems/walls-and-gates/discuss/72746/My-short-java-solution-very-easy-to-understand
*/
public void wallsAndGates(int[][] rooms) {
//DFS，不算很有效的方法
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;
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);
}
}