505. The Maze II

link

Same as 490 , just add heap for shortest path

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:

        m = len(maze)
        n = len(maze[0])

        self.res = False

        s = set()

        def dfs(i, j):
            if self.res:
                return

            if i == destination[0] and j == destination[1]:
                self.res = True
                return

            if (i, j) in s:
                return

            s.add((i, j))

            for x, y in [(0,1), (0,-1),(1,0),(-1,0)]:
                dx, dy = x, y
                
                while (0 <= i + dx < m and 0 <= j + dy < n) and maze[i+dx][j+dy] == 0:
                    dx += x
                    dy += y

                dfs(i+dx-x, j+dy-y)

        dfs(start[0], start[1])

        return self.res