8.19 - hard - 64

317 . Shortest Distance from All Buildings

典型的BFS的题目，BFS可以求得最短距离，所以很多碰到最小路径的时候可以考虑用BFS，还有这道题可以在访问的时候多记录一些信息，可以达到剪枝的效果

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = {} # building (i, j) -> {} # 0 x,y -> distance to i,j 
        count = 0
        total = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    total += 1
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    count += 1
                    building = (i, j)
                    m[building] = {}
                    if not self.bfs(grid, building, m, total):
                        return -1
        h = {}
        for key, val in m.iteritems():
            if not val:
                return -1
            for k, v in val.iteritems():
                if k in h:
                    h[k] = [h[k][0]+v, h[k][1]+1] # total steps, number of buildings reached
                else:
                    h[k] = [v, 1]
        if not h:
            return -1
        res = sys.maxint
        found = False
        for v in h.values():
            if v[1] == count:
                res = min(res, v[0])
                found = True
        if found:
            return res
        else:
            return -1
        
        
    def bfs(self, grid, building, m, total):
        dist = 0
        i, j = building
        count_building = 1
        visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
        visited[i][j] = True
        queue = [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]
        while queue: 
            l = len(queue)
            dist += 1
            for k in range(l):
                x, y = queue.pop(0)
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and not visited[x][y]:
                    visited[x][y] = True
                    if grid[x][y] == 0:
                        if (x, y) in m[building]:
                            continue
                        else:
                            m[building][(x,y)] = dist
                            queue += [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
                    elif grid[x][y] == 1:
                        count_building += 1
        return count_building == total