算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。是以，為了提高大家的算法能力，這個公衆号後續每天帶大家做一道算法題，題目就從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;
}
};
好了，今天的文章就到這裡，如果覺得有所收獲，請順手點個在看或者轉發吧，你們的支援是我最大的動力 。
上期推文：
LeetCode1-300題彙總，希望對你有點幫助！
LeetCode刷題實戰301：删除無效的括号
LeetCode刷題實戰302：包含全部黑色像素的最小矩陣
LeetCode刷題實戰303：區域和檢索 - 數組不可變
LeetCode刷題實戰304：二維區域和檢索 - 矩陣不可變
LeetCode刷題實戰305：島嶼數量II
LeetCode刷題實戰306：累加數
LeetCode刷題實戰307：區域和檢索 - 數組可修改
LeetCode刷題實戰308：二維區域和檢索 - 可變
LeetCode刷題實戰309：最佳買賣股票時機含冷凍期
LeetCode刷題實戰310：最小高度樹
LeetCode刷題實戰311：稀疏矩陣的乘法
LeetCode刷題實戰312：戳氣球
LeetCode刷題實戰313：超級醜數
LeetCode刷題實戰314：二叉樹的豎直周遊
LeetCode刷題實戰315：計算右側小于目前元素的個數
LeetCode刷題實戰316：去除重複字母
