Leetcode 317. Shortest Distance from All Buildings （python+cpp）

题目

解法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;}}}}
};