Leetcode 317. Shortest Distance from All Buildings

• 題目
• 解法1：BFS
• 解法2：
• 二刷C++版本

題目

解法1：BFS

brutal force的從每一個空地出發，找與building的最短距離之和

class Solution:def shortestDistance(self, grid: List[List[int]]) -> int:def helper(i,j):visited = set()buildings = set()q = collections.deque()q.append((i,j,0))visited.add((i,j))total_step = 0dirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j,step = q.popleft()if grid[i][j] == 1 and (i,j) not in buildings:total_step += stepbuildings.add((i,j))if len(buildings) == num_buildings:breakif grid[i][j]!=1:for d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and (x,y) not in visited and grid[x][y]!=2:q.append((x,y,step+1))visited.add((x,y))return total_step if len(buildings)==num_buildings else -1m,n = len(grid),len(grid[0])num_buildings = 0for i in range(m):for j in range(n):if grid[i][j] == 1:num_buildings += 1min_step = float('inf')for i in range(m):for j in range(n):if grid[i][j] == 0:total_step = helper(i,j)if total_step!=-1 and min_step>total_step:min_step = total_stepreturn min_step if min_step!=float('inf') else -1

解法2：

根據題意來看，building數肯定是比空地數要少很多的，所以可以反向從building出發找每塊空地與這個building的距離，然后對于每個building都做同樣的事，將結果疊加找最小值

class Solution:def shortestDistance(self, grid: List[List[int]]) -> int:def bfs(i,j):visited = [[False]*n for _ in range(m)]q = collections.deque()q.append((i,j,1))dirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j,dis = q.popleft()for d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and not visited[x][y] and grid[x][y]==0:distance[x][y] += disreach_num[x][y] += 1q.append((x,y,dis+1))visited[x][y] = Truem,n = len(grid),len(grid[0])distance = [[0]*n for _ in range(m)]reach_num = [[0]*n for _ in range(m)]building_num = 0for i in range(m):for j in range(n):if grid[i][j] == 1:bfs(i,j)building_num += 1min_dist = float('inf')for i in range(m):for j in range(n):if grid[i][j]==0 and reach_num[i][j]==building_num:min_dist = min(min_dist,distance[i][j])return min_dist if min_dist!=float('inf') else -1

二刷C++版本

class Solution { public:int shortestDistance(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();// distance matrix for holding the sum of distance from current position// to all buildingsvector<vector<int>> dist(m,vector<int>(n,0));// matrix to check how many buildings can be reached from current positionvector<vector<int>> reached(m,vector<int>(n,0));// for every building position, we do bfs to find the minimum distance from// current building to every empty land. Update the dist and reached matrixint num_building = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 1){bfs(grid,dist,reached,i,j);num_building += 1;}}}// traverse dist and reached matrix, looking for the answerint ans = INT_MAX;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 0 && reached[i][j] == num_building){ans = min(ans,dist[i][j]);}}}return ans == INT_MAX ? -1 : ans;}void bfs(const vector<vector<int>>& grid, vector<vector<int>>& dist, vector<vector<int>>& reached, int i, int j){queue<vector<int>> q;q.push({i,j,0});vector<vector<int>> visited(grid.size(),vector<int>(grid[0].size(),0));visited[i][j] = 1;vector<vector<int>> dirs{{0,1},{0,-1},{1,0},{-1,0}};int x,y,next_x,next_y,step;while(!q.empty()){x = q.front()[0];y = q.front()[1];step = q.front()[2];q.pop();for(auto d : dirs){next_x = x + d[0];next_y = y + d[1];if(next_x >= 0 && next_x < grid.size() && next_y >= 0 && next_y < grid[0].size() && visited[next_x][next_y] == 0 && grid[next_x][next_y] == 0){q.push({next_x,next_y,step+1});visited[next_x][next_y] = 1;dist[next_x][next_y] += step + 1;reached[next_x][next_y] += 1;}}}} };

總結

以上是生活随笔為你收集整理的Leetcode 317. Shortest Distance from All Buildings （python+cpp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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