LC 0490 [M] The Maze - ALawliet/algorithms GitHub Wiki
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
Q = deque([start])
visited = set()
while Q:
r, c = Q.popleft()
if r == destination[0] and c == destination[1]:
return True
for dr, dc in [-1,0],[0,-1],[1,0],[0,1](/ALawliet/algorithms/wiki/-1,0],[0,-1],[1,0],[0,1):
nr, nc = r + dr, c + dc
# keep going until we hit a wall
while 0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and not maze[nr][nc]:
nr, nc = nr + dr, nc + dc
# when we exit the loop, we are in the wall, so need to backtrack to previous position
nr, nc = nr - dr, nc - dc
if (nr,nc) not in visited:
visited.add((nr,nc))
Q.append((nr,nc))
return False