Fast and Easy to Understand Python Solution


  • 0
    B

    My solution is different from the solutions posted so far in that it will try to terminate when the first BFS is done if the buildings are not connected to each other. Because of this, it beats almost 100% Python submissions so far. (~108ms)

    I also used a dictionary to store empty spaces and how many buildings they are connected to and the total distance from all buildings. This part can definitely be improved, not all empty spaces need to be stored in the dictionary.

    def shortestDistance(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            result = float('inf')
    
            def vaild_point(x, y, visited):
                if (x, y) in visited:
                    return -1
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 0:
                    return 0
                elif 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                    return 1
                return -1
            # number of all buildings
            n_buildings = sum(row.count(1) for row in grid)
            point_dict, connected, connected_building = {}, False, 1
            directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
            for i in xrange(len(grid)):
                for j in xrange(len(grid[0])):
                    if grid[i][j] == 1:
                        visited = set()
                        q = collections.deque()
                        q.append((i, j, 0))
                        visited = set()
                        visited.add((i, j))
                        while q:
                            x, y, dist = q.popleft()
                            for d in directions:
                                next_x, next_y = x+d[0], y+d[1]
                                if not connected and vaild_point(next_x, next_y, visited) == 1:
                                    connected_building += 1
                                    visited.add((next_x, next_y))
                                elif vaild_point(next_x, next_y, visited) == 0:
                                    visited.add((next_x, next_y))
                                    q.append((next_x, next_y, dist+1))
                                    # this part can be improved based on how many BFS' have already been done... Some points don't need to be added to the dictionary.
                                    if (next_x, next_y) not in point_dict:
                                        point_dict[(next_x, next_y)] = [1, dist+1]
                                    else:
                                        point_dict[(next_x, next_y)] = [point_dict[(next_x, next_y)][0]+1, point_dict[(next_x, next_y)][1]+dist+1]
                        # try to terminate early
                        if not connected and connected_building != n_buildings:
                            return -1
                        connected = True
            for key in point_dict:
                if point_dict[key][0] == n_buildings:
                    result = min(result, point_dict[key][1])
            return result if result != float('inf') else -1

Log in to reply
 

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