Walls and Gates

要点：

• 同样是bfs，这题可以用渲染的方法（即全部gate进初始q），注意区别Shortest Distance from All Buildings。那道题要找到某个点到"all" buildings的距离，所以不能用渲染，因为不是到该点的一条路径。而本题类似surrounded region，最终的最佳路径只取一条路径
• bfs的方法全是在展开后入q前更新
• 剪枝：只要值更新了，就一定是最小值。不用入q了

错误点：

• 忘了更新距离。因为gate是0，所以距离可以统一更新为从哪来的+1

# 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.from collections import dequeimport sysclass Solution(object):    def shortestDistance(self, grid):        """        :type grid: List[List[int]]        :rtype: int        """        def bfs(grid, m, n, x, y, total):            visited = [[False]*n for _ in xrange(m)] # error: don't use x,y            q = deque([(x,y)]) # error 1            count=0            dirs = [(1,0),(0,1),(-1,0),(0,-1)]            d = 0            while q:                ql = len(q) # error 2: use single object                d+=1                for _ in xrange(ql):                    x,y = q.popleft()                    for xd,yd in dirs:                        x0,y0 = x+xd,y+yd                        if 0<=x0