def hasPath(self, maze, start, destination): Q = [start] n = len(maze) m = len(maze) 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 and j == destination: 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
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
@whglamrock Thanks for pointing out! Popleft or DFS, both will give much better performance than pop(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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.