317 Shortest Distance from All Buildings

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.

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

思路： 我们用一个matrix来记录能到达i,j位置的building数和距离的和。然后对每一个grid值为1的点进行bfs就行了。

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        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))

grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
so = Solution()
a = so.shortestDistance(grid)
print a