Short (22line) Python Priority Queue Cheapest-First search


  • 0
    F

    Seems to be a short enough code, compared with other implementation

    Cheapest-First search, a variant of BFS

    from heapq import heappush, heappop
    class Solution(object):
        def shortestDistance(self, maze, start, destination):
            n, m = len(maze), len(maze[0])
            visited = set()
            queue = []
            direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
            heappush(queue, (0, start[0], start[1]) )
            while queue:
                length, x, y = heappop(queue)
                if x == destination[0] and y == destination[1]:
                    return length
                elif (x, y) not in visited:
                    visited.add((x,y))
                    for dx, dy in direction:
                        wl, wx, wy = length, x, y
                        while wx + dx >= 0 and wy + dy >= 0 and wx + dx < n and wy + dy < m and maze[wx + dx][wy + dy] == 0:
                            wx = wx + dx
                            wy = wy + dy
                            wl = wl + 1
                        heappush(queue, (wl, wx, wy))
            return -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.