Shortest Distance from All Buildings

Problem: Shortest Distance from All Buildings

In this problem, we can do breadth-first search from each building and add distance from this building to a empty land to that land. After we deal with all the buildings, we can know the distance from all buildings of each empty land so that we can get the answer.

Note that we need to check whether all the buildings can be reached from a certain empty land.

Code in Python:

from collections import deque

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        dists, visited_nums, building_num = {}, {}, 0
        min_dist = float("inf")

        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 1:
                    building_num += 1
                    queue = collections.deque()
                    queue.append((i, j, 0))
                    visited = {}
                    while queue:
                        x, y, dist = queue.popleft()
                        if (x+1,y) not in visited and x < m-1 and grid[x+1][y] == 0:
                            dists[(x+1, y)] = dists.get((x+1, y), 0) + dist + 1
                            visited_nums[(x+1, y)] = visited_nums.get((x+1, y), 0) + 1
                            visited[(x+1, y)] = True
                            queue.append((x+1, y, dist+1))
                        if (x-1,y) not in visited and x > 0 and grid[x-1][y] == 0:
                            dists[(x-1, y)] = dists.get((x-1, y), 0) + dist + 1
                            visited_nums[(x-1, y)] = visited_nums.get((x-1, y), 0) + 1
                            visited[(x-1, y)] = True
                            queue.append((x-1, y, dist+1))
                        if (x,y+1) not in visited and y < n-1 and grid[x][y+1] == 0:
                            dists[(x, y+1)] = dists.get((x, y+1), 0) + dist + 1
                            visited_nums[(x, y+1)] = visited_nums.get((x, y+1), 0) + 1
                            visited[(x, y+1)] = True
                            queue.append((x, y+1, dist+1))
                        if (x,y-1) not in visited and y > 0 and grid[x][y-1] == 0:
                            dists[(x, y-1)] = dists.get((x, y-1), 0) + dist + 1
                            visited_nums[(x, y-1)] = visited_nums.get((x, y-1), 0) + 1
                            visited[(x, y-1)] = True
                            queue.append((x, y-1, dist+1))

        for x, y in dists:
            if dists[(x, y)] < min_dist and visited_nums[(x, y)] == building_num:
                min_dist = dists[(x, y)]

        if min_dist == float("inf"):
            return -1

        return min_dist