Python solution 72ms beats 100%, BFS with pruning


  • 12
    K

    Use hit to record how many times a 0 grid has been reached and use distSum to record the sum of distance from all 1 grids to this 0 grid. A powerful pruning is that during the BFS we use count1 to count how many 1 grids we reached. If count1 < buildings then we know not all 1 grids are connected are we can return -1 immediately, which greatly improved speed (beat 100% submissions).

    def shortestDistance(self, grid):
        if not grid or not grid[0]: return -1
        M, N, buildings = len(grid), len(grid[0]), sum(val for line in grid for val in line if val == 1)
        hit, distSum = [[0] * N for i in range(M)], [[0] * N for i in range(M)]
        
        def BFS(start_x, start_y):
            visited = [[False] * N for k in range(M)]
            visited[start_x][start_y], count1, queue = True, 1, collections.deque([(start_x, start_y, 0)])
            while queue:
                x, y, dist = queue.popleft()
                for i, j in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= i < M and 0 <= j < N and not visited[i][j]:
                        visited[i][j] = True
                        if not grid[i][j]:
                            queue.append((i, j, dist + 1))
                            hit[i][j] += 1
                            distSum[i][j] += dist + 1
                        elif grid[i][j] == 1:
                            count1 += 1
            return count1 == buildings  
        
        for x in range(M):
            for y in range(N):
                if grid[x][y] == 1:
                    if not BFS(x, y): return -1
        return min([distSum[i][j] for i in range(M) for j in range(N) if not grid[i][j] and hit[i][j] == buildings] or [-1])

  • 2
    E
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        if m: n = len(grid[0])
        if not m or not n:
            return -1
        dist = [[0]*n for i in range(m)]
        totalB = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1: totalB+=1
        ## do BFS from each building, and decrement all empty place for every building visit
        ## when grid[i][j] == -totalB, it means that grid[i][j] are already visited from all buildings
        ## and use dist to record distances from buildings
        def bfs(i, j, bIndex):
            queue = collections.deque([(i, j, 0)])
            while queue:
                i, j, d = queue.popleft()
                for x,y in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
                    if 0<=x<m and 0<=y<n and grid[x][y]==bIndex:
                        dist[x][y] += d+1
                        grid[x][y] -= 1
                        queue.append((x, y, d+1))
        
        bIndex = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    bfs(i, j, bIndex)
                    bIndex -= 1
        res = [dist[i][j] for i in range(m) for j in range(n) if grid[i][j]+totalB==0]
        return min(res) if res else -1
    

  • 0
    E

    solution based on PO and @StefanPochmann


  • 0
    J

    Best solution!


  • 2

    Another BFS clear solution with same idea.
    Using matrix to count the sum of distance and number of building have visited this position

    class Solution(object):
        def shortestDistance(self, grid):
            if not grid or not grid[0]:
                return -1
    
            matrix = [[[0,0] for i in range(len(grid[0]))] for j in range(len(grid))]
    
            cnt = 0    # count how many building we have visited
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 1:
                        self.bfs([i,j], grid, matrix, cnt)
                        cnt += 1
    
            res = float('inf')
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    if matrix[i][j][1]==cnt:
                        res = min(res, matrix[i][j][0])
    
            return res if res!=float('inf') else -1
    
        def bfs(self, start, grid, matrix, cnt):
            q = [(start, 0)]
            while q:
                tmp = q.pop(0)
                po, step = tmp[0], tmp[1]
                for dp in [(-1,0), (1,0), (0,1), (0,-1)]:
                    i, j = po[0]+dp[0], po[1]+dp[1]
                    # only the position be visited by cnt times will append to queue
                    if 0<=i<len(grid) and 0<=j<len(grid[0]) and matrix[i][j][1]==cnt and grid[i][j]==0:
                        matrix[i][j][0] += step+1
                        matrix[i][j][1] = cnt+1
                        q.append(([i,j], step+1))
    

  • 0

    The idea is great but the code style is really bad


  • 0
    D

    For the sake a better clarify.

    import itertools
    import Queue
    
    
    inf_ = (1 << 31) - 1
    
    LAND = 0
    BUILDING = 1
    WALL = 2
    
    
    class Solution(object):
        def bfs(self, grid, s_i, s_j, total_buildings):
            n = len(grid)
            m = len(grid[0])
            dist = [
                [inf_ for j in range(m)]
                for i in range(n)
            ]
            dist[s_i][s_j] = 0
            que = Queue.Queue()
            seen = set((s_i, s_j))
            que.put((s_i, s_j))
            buildings_seen = {(s_i, s_j)}
            
            while not que.empty():
                i, j = que.get()
                for d_i, d_j in {(-1, 0), (1, 0), (0, 1), (0, -1)}:
                    n_i, n_j = i + d_i, j + d_j
                    if n_i < 0 or n_i >= n or n_j < 0 or n_j >= m:
                        continue
                    if (n_i, n_j) in seen:
                        continue
                    if grid[n_i][n_j] == BUILDING:
                        buildings_seen.add((n_i, n_j))
                    if grid[n_i][n_j] != LAND:
                        continue
                    dist[n_i][n_j] = dist[i][j] + 1
                    que.put((n_i, n_j))
                    seen.add((n_i, n_j))
            if len(buildings_seen) != total_buildings:
                return None
            return dist
    
        def shortestDistance(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            if not grid or not grid[0]:
                return 0
            n = len(grid)
            m = len(grid[0])
            accu_dist = [
                [0 for j in range(m)]
                for i in range(n)
            ]
            count_reachable = [
                [0 for j in range(m)]
                for i in range(n)
            ]
    
            count_building = 0
            for i, j in itertools.product(range(n), range(m)):
                if grid[i][j] == BUILDING:
                    count_building += 1
    
            for i, j in itertools.product(range(n), range(m)):
                if grid[i][j] != BUILDING:
                    continue
                dist = self.bfs(grid, i, j, count_building)
                if not dist:
                    return -1
                for i_, j_ in itertools.product(range(n), range(m)):
                    if grid[i_][j_] == LAND and dist[i_][j_] != inf_:
                        accu_dist[i_][j_] += dist[i_][j_]
                        count_reachable[i_][j_] += 1
    
            ans = inf_
            for i, j in itertools.product(range(n), range(m)):
                if grid[i][j] == LAND and count_reachable[i][j] == count_building:
                    ans = min(ans, accu_dist[i][j])
            return ans if ans != inf_ else -1
    
    
    assert Solution().shortestDistance([
        [1,0,2,0,1],
        [0,0,0,0,0],
        [0,0,1,0,0],
    ]) == 7
    

Log in to reply
 

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