Google
317 Shortest Distance from All Buildings

1. Question

You want to build a house on anemptyland which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
  • Each 0 marks an empty land which you can pass by freely.
  • Each 1 marks a building which you cannot pass through.
  • Each 2 marks an obstacle which you cannot pass through.
For example, given three buildings at(0,0),(0,4),(2,2), and an obstacle at(0,2):
1
1 - 0 - 2 - 0 - 1
2
| | | | |
3
0 - 0 - 0 - 0 - 0
4
| | | | |
5
0 - 0 - 1 - 0 - 0
Copied!
The point(1,2)is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.
Note: There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

2. Implementation

(1) BFS
1
class Solution {
2
public int shortestDistance(int[][] grid) {
3
if (grid == null || grid.length == 0) {
4
return -1;
5
}
6
7
int m = grid.length;
8
int n = grid[0].length;
9
10
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
11
12
int[][] distance = new int[m][n];
13
int[][] reach = new int[m][n];
14
15
int buildings = 0;
16
17
for (int i = 0; i < m; i++) {
18
for (int j = 0; j < n; j++) {
19
if (grid[i][j] == 1) {
20
++buildings;
21
getDistanceByBFS(i, j, distance, reach, directions, grid);
22
}
23
}
24
}
25
26
int res = Integer.MAX_VALUE;
27
for (int i = 0; i < m; i++) {
28
for (int j = 0; j < n; j++) {
29
if (grid[i][j] == 0 && reach[i][j] == buildings) {
30
res = Math.min(res, distance[i][j]);
31
}
32
}
33
}
34
return res == Integer.MAX_VALUE ? -1 : res;
35
}
36
37
public void getDistanceByBFS(int row, int col, int[][] distance, int[][] reach, int[][] directions, int[][] grid) {
38
int m = grid.length;
39
int n = grid[0].length;
40
41
boolean[][] visited = new boolean[m][n];
42
43
Queue<int[]> queue = new LinkedList<>();
44
queue.add(new int[] {row, col});
45
46
int dist = 0;
47
48
while (!queue.isEmpty()) {
49
++dist;
50
int size = queue.size();
51
52
for (int i = 0; i < size; i++) {
53
int[] curCell = queue.remove();
54
55
for (int[] direction : directions) {
56
int nextRow = curCell[0] + direction[0];
57
int nextCol = curCell[1] + direction[1];
58
59
if (isValid(nextRow, nextCol, visited, grid)) {
60
distance[nextRow][nextCol] += dist;
61
reach[nextRow][nextCol] += 1;
62
queue.add(new int[] {nextRow, nextCol});
63
visited[nextRow][nextCol] = true;
64
}
65
}
66
}
67
}
68
}
69
70
public boolean isValid(int row, int col, boolean[][] visited, int[][] grid) {
71
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && !visited[row][col] && grid[row][col] == 0;
72
}
73
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(M^2N^2),BFS的时间复杂度是O(mn), 总的时间复杂度是 O(# of buildings ) * O(mn), 最坏的情况是每个cell都是building, 总的时间复杂度为O(mn) * O(mn) => O(m^2n^2), 空间复杂度O(mn)