8.23 - hard - 96

499. The Maze III

想法很简单，有点懒得写。
在heap里存上 dist，path，cur_pos, 然后再用一个visited来防止重复访问，不过这题答案的写法很巧妙，多练习几次

class Solution(object):
    def findShortestWay(self, maze, ball, hole):
        """
        :type maze: List[List[int]]
        :type ball: List[int]
        :type hole: List[int]
        :rtype: str
        """
        A = maze
        ball, hole = tuple(ball), tuple(hole)
        R, C = len(A), len(A[0])

        def neighbors(r, c):
            for dr, dc, di in [(-1, 0, 'u'), (0, 1, 'r'), 
                               (0, -1, 'l'), (1, 0, 'd')]:
                cr, cc, dist = r, c, 0
                while (0 <= cr + dr < R and 
                        0 <= cc + dc < C and
                        not A[cr+dr][cc+dc]):
                    cr += dr
                    cc += dc
                    dist += 1
                    if (cr, cc) == hole:
                        break
                yield (cr, cc), di, dist

        pq = [(0, '', ball)]
        seen = set()
        while pq:
            dist, path, node = heapq.heappop(pq)
            if node in seen: continue
            if node == hole: return path
            seen.add(node)
            for nei, di, nei_dist in neighbors(*node):
                heapq.heappush(pq, (dist+nei_dist, path+di, nei) )

        return "impossible"