Python BFS solution

  • 9
    def hasPath(self, maze, start, destination):
            Q = [start]
            n = len(maze)
            m = len(maze[0])
            dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
            while Q:
                # Use Q.pop() as DFS or Q.popleft() with deque from collections library for better performance. Kudos to @whglamrock
                i, j = Q.pop(0)
                maze[i][j] = 2
                if i == destination[0] and j == destination[1]:
                    return True
                for x, y in dirs:
                    row = i + x
                    col = j + y
                    while 0 <= row < n and 0 <= col < m and maze[row][col] != 1:
                        row += x
                        col += y
                    row -= x
                    col -= y
                    if maze[row][col] == 0:
                        Q.append([row, col])
            return False

  • 1

    A brilliant, simple solution!!!

    Is it better to use deque to popleft instead of always pop(0)?

    Or we can simply use pop(), then your solution just turned into DFS... which also got AC, lol

  • 0

    @whglamrock Thanks for pointing out! Popleft or DFS, both will give much better performance than pop(0) :)

  • 0

    Nice, I like the use of dirs for eliminating a lot of duplicate code.

    It would be better to mark nodes when adding them to the queue rather than when they are popped. Currently your code is adding and processing the same node more than once if more than one of its neighbors is processed before it.

  • 0

    why maze[i][j] = 2?
    thank you

Log in to reply

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