317.Shortest Distance from All Buildings

Tags: [graph], [BFS], [matrix], [grid]

Com: {g}

Link: https://leetcode.com/problems/shortest-distance-from-all-buildings/#/description

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0,1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at(0,0),(0,4),(2,2), and an obstacle at(0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point(1,2)is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Solution: BFS

from collections import deque

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return -1

        num_of_rows = len(grid)
        num_of_cols = len(grid[0])

        distances = [[[] for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        building_counter = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if grid[row][col] == 1:
                    building_counter += 1
                    self.bfs(grid, num_of_rows, num_of_cols, row, col, distances)

        min_distance = sys.maxint
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if grid[row][col] == 0 and len(distances[row][col]) == building_counter:
                    min_distance = min(min_distance, sum(distances[row][col]))

        return min_distance if 0 < min_distance < sys.maxint else -1

    def bfs(self, grid, num_of_rows, num_of_cols, curr_row, curr_col, distances):
        distance_map = [[0 for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        queue = deque()
        queue.append((curr_row, curr_col))
        while queue:
            row, col = queue.popleft()
            distance = distance_map[row][col]

            # top
            if row - 1 >= 0 and grid[row - 1][col] == 0 and distance_map[row - 1][col] == 0:
                distance_map[row - 1][col] = distance + 1
                queue.append((row - 1, col))

            # left
            if col - 1 >= 0 and grid[row][col - 1] == 0 and distance_map[row][col - 1] == 0:
                distance_map[row][col - 1] = distance + 1
                queue.append((row, col - 1))

            # bottom
            if row + 1 < num_of_rows and grid[row + 1][col] == 0 and distance_map[row + 1][col] == 0:
                distance_map[row + 1][col] = distance + 1
                queue.append((row + 1, col))

            # right
            if col + 1 < num_of_cols and grid[row][col + 1] == 0 and distance_map[row][col + 1] == 0:
                distance_map[row][col + 1] = distance + 1
                queue.append((row, col + 1))

        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if grid[row][col] == 0 and distance_map[row][col] > 0:
                    distances[row][col].append(distance_map[row][col])

Revelation:

• Checking len(distances[row][col]) == building_counter, which guarantees the current space[row][col] can access all buildings.
• In the BFS, checking distance_map[row][col] > 0, is because each BFS starts from a building, if it cannot access to any empty space, the value of distance_map[row][col] will be 0.

Note:

• Time complexity = O(num_of_buildings * num_of_empty_spaces).
• Space complexity = O(n + n) = O(n), n is the total number of elements in grid. Because the distance_map in BFS function, each time BFS function terminates, the program will release that part of space. Think about if we write the whole BFS logic just in the main function, each time before we start BFS, we clear the distance_map, so the total space complexity = O(n + n) = O(n).