https://leetcode.com/problems/the-maze-ii/#/description

bfs solution with queue

class Solution(object):
    def shortestDistance(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        m = len(maze)
        n = len(maze[0])
        res = None

        def go(start, direction):
            # return the stop position and length
            i, j = start
            x, y = direction
            l = 0
            while 0 <= i + x < m and 0 <= j + y < n and maze[i + x][j + y] != 1:
                i += x
                j += y
                l += 1
            return l, (i, j)

        # bfs (dijkstra: https://en.wikipedia.org/wiki/Dijkstra's_algorithm)
        visited = {}
        q = [(0, tuple(start))]
        while q:
            length, cur = q.pop(0)
            if cur in visited and visited[cur] <= length:
                continue  # if cur is visited and with a shorter length, skip it.
            # visited all its neighbors
            for direction in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                l, np = go(cur, direction)
                q.append((length + l, np))  # push it into queue
            # mark it as visited
            visited[cur] = length
        if tuple(destination) not in visited:
            return -1
        else:
            return visited[tuple(destination)]

bfs solution with heap(PQ)

class Solution(object):
    def shortestDistance(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        m=len(maze)
        n=len(maze[0])
        res=None 
        def go(start, direction):
            # return the stop position and length
            i, j = start
            x, y= direction
            l=0
            while 0 <= i+x < m and 0 <= j+y < n and maze[i+x][j+y] != 1:
                i += x
                j += y
                l +=1
            return l, (i,j)
        # bfs (dijkstra: https://en.wikipedia.org/wiki/Dijkstra's_algorithm)
        visited={}
        q=[]
        heapq.heappush(q, (0, tuple(start)))
        while q: 
            length, cur = heapq.heappop(q)
            if cur in visited:
                continue # if 'cur' is visited skip it.
            # the length with 'cur' is the shotest path from start to 'cur'
            if cur == tuple(destination):
                return length
            # visited all its neighbors
            for direction in [(-1, 0), (1, 0), (0,-1), (0,1)]:
                l, np = go(cur, direction)
                heapq.heappush(q, (length+l, np)) # push it into queue
            # mark it as visited, 'length' is the shortest path from start to 'cur'
            visited[cur] = length  
        return -1