leetcode 317

问题

You want to build a house on an empty land 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.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             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.

分析

从每个为1的点进行广度优先搜索，计算出它到每一个为0的点的距离，累加到该dist数组上，同时统计出每个为0的点所能到达的1的点的个数的总和。遍历所有为0且能够到达1的点的个数为1个总和的点，统计出其最小值。

代码

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
57
58
class Solution {
public:
    vector<vector<int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int shortestDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        if (m == 0 || n == 0)
            return -1;
        vector<vector<int>> reached(m, vector<int>(n, 0));
        vector<vector<int>> dist(m, vector<int>(n, 0));
        int totalBuildings = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    bfs(grid, i, j, reached, dist);
                    totalBuildings++;
                }
            }
        }

        int ans = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (reached[i][j] == totalBuildings)
                    ans = min(ans, dist[i][j]);
            }
        }
        return ans==INT_MAX || totalBuildings == 0? -1: ans;
    }
    void bfs(vector<vector<int>> &grid, int x, int y, vector<vector<int>> &reached, vector<vector<int>> &dist) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> v(m, vector<bool>(n, false));
        queue<pair<int,int>> q;
        q.push({x,y});
        int d = 0;
        while (q.size()!=0) {
            d++;
            int size = q.size();
            while (size--) {
                int x0 = q.front().first;
                int y0 = q.front().second;
                q.pop();
                for (vector<int>  &dir: dirs) {
                    int x1 = x0+dir[0];
                    int y1 = y0+dir[1];
                    if (x1<0 || x1 >= m || y1<0 || y1>=n || 
                        grid[x1][y1]!=0 || v[x1][y1] == true)
                        continue;
                    v[x1][y1] = true;
                    reached[x1][y1]++;
                    dist[x1][y1] += d;
                    q.push({x1, y1});
                }
            }
        }
    }
};