题目描述

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.

样例

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.

最直观的想法是模拟：遍历每一个0，累加从该0出发到所有1的距离和，时间复杂度是$O(m^2n^2)$，会超时

换一个思路，改变BFS的起点，从1出发，每一层BFS记录该点出发沿路0的最短距离，同时有一个全局变量total记录矩阵中0到所有1的最短距离，因为BFS保证了当前0就是本层1的最短距离，所以无须比较直接把当前最短距离累加到全局最短距离即可

第二个思路的时间复杂度也是$O(m^2n^2)$，但是题目的大型样例0多1少，第二个思路会比第一个思路快非常多

值得一提的是，代码中walk变量，随着每层BFS递减，它表示当前层访问位置的层深；同时每层被访问的0递减，如果有一个1被其他1,2挡住，那势必会让后续层的层深和walk出现差距，由此保证了对于无解情况的侦查，同时去重

时间复杂度

参考文献：leetcode题解by StefanPochmann

C++ 代码

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int res=-1, m=grid.size(), n=grid[0].size(), walk=0;
        vector<vector<int>> ds={{1,0},{0,1},{-1,0},{0,-1}};
        auto total=grid;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++){
                if(grid[i][j]==1){
                    res=-1;
                    queue<int> q;
                    auto dist=grid;
                    q.push(i*n+j);
                    while(q.size()){
                        auto cur=q.front(); q.pop();
                        int r=cur/n, c=cur%n;
                        for(auto d:ds){
                            int nr=r+d[0], nc=c+d[1];
                            if(nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==walk){
                                grid[nr][nc]--;
                                dist[nr][nc]=dist[r][c]+1;
                                total[nr][nc]+=dist[nr][nc]-1;
                                q.push(nr*n+nc);
                                if(!~res || res>total[nr][nc])
                                    res=total[nr][nc];
                            }
                        }    
                    }
                    walk--;
                }
            }

        return res;
    }
};