LeetCode刷题实战317：离建筑物最近的距离-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 离建筑物最近的距离，我们先来看题面：

https://leetcode-cn.com/problems/shortest-distance-from-all-buildings/

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.

你是个房地产开发商，想要选择一片空地建一栋大楼。你想把这栋大楼够造在一个距离周边设施都比较方便的地方，通过调研，你希望从它出发能在最短的距离和内抵达周边全部的建筑物。请你计算出这个最佳的选址到周边全部建筑物的最短距离和。

注意：

你只能通过向上、下、左、右四个方向上移动。

给你一个由 0、1 和 2 组成的二维网格，其中：

0 代表你可以自由通过和选择建造的空地

1 代表你无非通行的建筑物

2 代表你无非通行的障碍物

示例

解题

主要思路：

（1）使用广度优先搜索，从每个建筑出发，找能到达的各个空地的距离，从所有建筑都能到达的空地中选择一个距离最小的值；

（2）使用两个数组进行辅助，一个用来辅助记录从建筑出发的到各个空地的距离，一个用来辅助记录各个建筑到某个空地的距离和，最后从其中选择一个所有的建筑都能到达的空地的最小值作为结果；

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int rows=grid.size();
        int cols=grid[0].size();
        //记录各个建筑到各个空格的距离
        vector<vector<int>> dist(rows,vector<int>(cols,0));
        //记录各个建筑能到各个空格的距离之和
        vector<vector<int>> sum_dist(rows,vector<int>(cols,0));
        //可以移动的方向
        vector<vector<int>> step={{0,1},{0,-1},{1,0},{-1,0}};
        //主要标识之前的各个建筑都能到达的空格，这样减少计算量
        int times=0;
        int res=INT_MAX;//从当前各个建筑都能到达的空地中，找出最小的距离之和值
        //遍历各个位置
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                if(grid[i][j]==1){//若当前位置是建筑，从该位置开始进行广度优先搜索
                    res=INT_MAX;//初始化该值
                    pair<int,int> cur_pos;//辅助变量
                    queue<pair<int,int>> q;//广度优先搜索存储结构
                    q.push({i,j});//初始化
                    while(!q.empty()){
                        cur_pos=q.front();//当前点
                        q.pop();
                        for(int k=0;k<step.size();++k){//尝试的四个方向
                          //尝试的位置
                            int x=cur_pos.first+step[k][0];
                            int y=cur_pos.second+step[k][1];
                            //若当前位置没有越界，既有效，且之前的各个建筑都能够到达
                            if(x>=0&&x<rows&&y>=0&&y<cols&&grid[x][y]==times){
                              //则更新当前距离
                                dist[x][y]=dist[cur_pos.first][cur_pos.second]+1;
                                //更新对应的距离之和
                                sum_dist[x][y]+=dist[x][y];
                                //保存最小的距离和
                                res=min(res,sum_dist[x][y]);
                                //对应的值减一，标识当前建筑也访问过
                                --grid[x][y];
                                //压入当前位置
                                q.push({x,y});
                            }
                        }
                    }
                    //若该值没有变化，说明该建筑不能到达之前建筑都到达过的空地，则直接返回-1
                    if(res==INT_MAX){
                        return -1;
                    }
                    //标识当前建筑也访问过
                    --times;
                }
            }
        }
        return res;
    }
};