Clean BFS python solution with explanation


  • 0
    L
    import copy
    from collections import deque
    
    
    class Solution(object):
        def shortestDistance(self, grid):
            """
            the basic idea is to do BFS for all buildings to those empty land(the empty should be reachable by
            previous buildings), each BFS we can get the smallest distance from the BFS building to all valid empty land,
            we sum the distance from empty land to building up we can get the distance required if we set the house in
            the empty land, we return the smallest distance
    
            :type grid: List[List[int]]
            :rtype: int
            """
            if not grid:
                return 0
            m, n = len(grid), len(grid[0])
            sum_grid = copy.deepcopy(grid)
            res = 0
            empty_land_val = 0
            for i, row in enumerate(grid):
                for j, ele in enumerate(row):
                    if ele == 1:
                        queue = deque([(i, j)])
                        dist = copy.deepcopy(grid)
                        res = float("inf")
                        # BFS for each building to compute dist this building need to reach valid empty land(
                        # valid means previous building can also reach this empty land), then add up the dist
                        while len(queue) > 0:
                            a, b = queue.pop()
                            for I, J in (a, b + 1), (a, b - 1), (a + 1, b), (a - 1, b):
                                if 0 <= I < m and 0 <= J < n and grid[I][J] == empty_land_val:
                                    # compute the empty land smallest dist to the cur building
                                    dist[I][J] = dist[a][b] + 1
                                    # sum up with the dist which this empty land need to reach other building
                                    sum_grid[I][J] += dist[I][J] - 1
                                    queue.appendleft((I, J))
                                    # next round grid[I][J] is the value of empty_land
                                    grid[I][J] -= 1
                                    res = min(res, sum_grid[I][J])
                        empty_land_val -= 1
                        # if res doesn't change, this means this building cant reach any valid empty land, so return -1
                        if res == float("inf"):
                            return -1
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.