317 Shortest Distance from All Buildings

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)

681 Next Closest Time

587 Erect the Fence

Last modified 2yr ago

Copy link

Contents

317. Shortest Distance from All Buildings

1. Question

2. Implementation

3. Time & Space Complexity

317. Shortest Distance from All Buildings​

1. Question

2. Implementation

3. Time & Space Complexity

317. Shortest Distance from All Buildings