?LeetCode刷題實戰(zhàn)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.
示例
解題
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){//若當前位置是建筑，從該位置開始進行廣度優(yōu)先搜索
res=INT_MAX;//初始化該值
pair<int,int> cur_pos;//輔助變量
queue<pair<int,int>> q;//廣度優(yōu)先搜索存儲結(jié)構(gòu)
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;
//更新對應(yīng)的距離之和
sum_dist[x][y]+=dist[x][y];
//保存最小的距離和
res=min(res,sum_dist[x][y]);
//對應(yīng)的值減一，標識當前建筑也訪問過
--grid[x][y];
//壓入當前位置
q.push({x,y});
}
}
}
//若該值沒有變化，說明該建筑不能到達之前建筑都到達過的空地，則直接返回-1
if(res==INT_MAX){
return -1;
}
//標識當前建筑也訪問過
--times;
}
}
}
return res;
}
};
評論
圖片
表情