Leetcode #317:離建筑物最近的距離

• 題目
• • 題干
  • 示例
• 題解
• • Python
  • C++

題目

題干

該問題離建筑物最近的距離 題面：

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:
輸入: [[1, 0, 2, 0, 1], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0]]
輸出: 7
解釋:
給定三個建筑物(0,0)、(0,4)和(2,2)以及一個位于(0,2)的障礙物。
由于總距離之和3+3+1=7最優，所以位置(1,2)是符合要求的最優地點，故返回7。
注意： 你會保證有至少一棟建筑物，如果無法按照上述規則返回建房地點，則返回-1。

題解

主要思路：
（1）使用廣度優先搜索，從每個建筑出發，找能到達的各個空地的距離，從所有建筑都能到達的空地中選擇一個距離最小的值；
（2）使用兩個數組進行輔助，一個用來輔助記錄從建筑出發的到各個空地的距離，一個用來輔助記錄各個建筑到某個空地的距離和，最后從其中選擇一個所有的建筑都能到達的空地的最小值作為結果；

Python

import sys INT_MAX = sys.maxsizeclass Solution:def __init__(self, grids):self.grids = gridsdef short_dis(self):rows = len(self.grids)cols = len(self.grids[0])# 記錄各建筑到各空格距離dist = [[0] * cols for i in range(rows)]# 記錄各建筑到各空格距離之和sum_dist = [[0] * cols for i in range(rows)]# 可以移動的方向step = [(0, 1), (0, -1), (1, 0), (-1, 0)]# 標識之前的各建筑都能到達的空格，減少計算量times = 0res = INT_MAXfor i in range(rows):for j in range(cols):if self.grids[i][j] == 1: # 若當前位置是建筑，從該位置開始進行廣度優先搜索res = INT_MAXq = [(i, j)] # 廣度優先搜索存儲結構while len(q) > 0:cur_pos = q.pop(0) # 輔助變量，當前點for k in range(len(step)): # 嘗試的四個方向# 當前位置x = cur_pos[0] + step[k][0]y = cur_pos[1] + step[k][1]# 若當前位置沒有越界，既有效，且之前的各個建筑都能夠到達if 0 <= x < rows and 0 <= y < cols and self.grids[x][y] == times:# 則更新當前距離dist[x][y] = dist[cur_pos[0]][cur_pos[1]] + 1# 更新對應的距離之和sum_dist[x][y] += dist[x][y]# 保存最小的距離和res = min(res, sum_dist[x][y])# 對應的值減一，標識當前建筑也訪問過self.grids[x][y] -= 1# 壓入當前位置q.append([x, y])# 若該值沒有變化，說明該建筑不能到達之前建筑都到達過的空地，則直接返回 - 1if res == INT_MAX:return -1# 標識當前建筑也訪問過times -= 1return res

C++

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});}}}//若該值沒有變化，說明該建筑不能到達之前建筑都到達過的空地，則直接返回-1if(res==INT_MAX){return -1;}//標識當前建筑也訪問過--times;}}}return res;} };

總結

以上是生活随笔為你收集整理的Leetcode #317:离建筑物最近的距离的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。