今天和大家聊的问题叫做 离建筑物最近的距离，我们先来看题面：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; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
