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
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
private int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public int shortestDistance(int[][] grid) {
int[][][] gridSumCount = new int[grid.length][grid[0].length][2];
Deque<int[]> buildings = new ArrayDeque<>();
int buildingCount = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
buildings.offer(new int[] { i, j });
buildingCount += 1;
}
}
}
while (!buildings.isEmpty()) {
int[] currBuilding = buildings.poll();
Deque<int[]> possibleSites = new ArrayDeque<>();
possibleSites.offer(currBuilding);
boolean[][] visited = new boolean[grid.length][grid[0].length];
visited[currBuilding[0]][currBuilding[1]] = true;
int steps = 1;
while (!possibleSites.isEmpty()) {
int size = possibleSites.size();
for (int i = 0; i < size; i++) {
int[] currPos = possibleSites.poll();
for (int[] direction : DIRECTIONS) {
int newRow = currPos[0] + direction[0];
int newCol = currPos[1] + direction[1];
if (!isOutOfBound(grid, newRow, newCol) && grid[newRow][newCol] == 0
&& !visited[newRow][newCol]) {
gridSumCount[newRow][newCol][0] += steps;
gridSumCount[newRow][newCol][1] += 1;
visited[newRow][newCol] = true;
possibleSites.offer(new int[] { newRow, newCol });
}
}
}
steps += 1;
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0 && gridSumCount[i][j][1] == buildingCount) {
ans = Math.min(ans, gridSumCount[i][j][0]);
}
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private boolean isOutOfBound(int[][] grid, int row, int col) {
return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
}
}
|
From building to empty spaces.
注意的是level traversal的时候, for循环条件不能写成i < possibleSites.size(), 因为每次for完后, possibleSites的size会变. 但是可以让i = possibleSites.size(); i > 0; i–这样. 这一点我找了好久.
淦!
时间复杂度: O(m^2 * n^2)
空间复杂度: O(m * n)
还可以更简洁, 就是把bfs封装成函数, 数building数目那里直接调用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
| class Solution {
private final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public int shortestDistance(int[][] grid) {
int targetSpotValue = 0;
int[][] total = new int[grid.length][grid[0].length];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
ans = Integer.MAX_VALUE;
Deque<int[]> emptySpots = new ArrayDeque<>();
emptySpots.offer(new int[] { i, j });
int steps = 1;
while (!emptySpots.isEmpty()) {
for (int k = emptySpots.size(); k > 0; k--) {
int[] currPos = emptySpots.poll();
for (int[] direction : DIRECTIONS) {
int newRow = currPos[0] + direction[0];
int newCol = currPos[1] + direction[1];
if (!isOutOfBound(grid, newRow, newCol) && grid[newRow][newCol] == targetSpotValue) {
total[newRow][newCol] += steps;
grid[newRow][newCol] -= 1;
emptySpots.offer(new int[] { newRow, newCol });
ans = Math.min(ans, total[newRow][newCol]);
}
}
}
steps += 1;
}
targetSpotValue -= 1;
}
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private boolean isOutOfBound(int[][] grid, int row, int col) {
return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
}
}
|
这是第二种解法. 对于每个1, 我们都要BFS. 那么我们就要标记visited过的地方. 如何标记呢? 我们就把visited过的地方减去1. 对于第一次BFS, 我们要找的就是是0的位置, 找到后把0变为-1然后在我们的额外二维数组中在对应位置加上目前的1到这个0需要的步数. 等到第二次BFS, 之前能被第一个BFS到达的地方都被标记上了-1, 于是我们就要找是-1的格子(是0的格子表示这个点不能到达第一个BFS的1, 因此它不可能为我们的答案, 我们的答案应该是所有1都能到达). 找到-1格子把它变为-2, 然后在total中对应位置更新距离. 这样就在原二维数组上标记去过的地方了.
同时我们也能在一次遍历后就得到答案, 做法就是在每次BFS的时候, 记录此次哪个位置目前的sum最小, 我们总会到最后一次BFS, 那么最后一次记录的ans就是答案, 之前的记录都不是答案, 只是最后一次BFS的答案是我们想要的.
时间复杂度: O(M^2N^2) 因为我们要对每个1都BFS, 一次BFS是O(MN), 一共MN个元素, 那就是O(M^2N^2)
空间复杂度: O(mn) 我们用total来存空地到每个1的sum是多少.
