BFS solution is easier to understand
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
# time O(MN) space O(MN)
# step1, dir cache; track visited ;q; initialize start
# step2: iterate q, termination condition: element on top q == destination
# step3: current pos, go 4 dirs, each dir go all the way to wall,
# step4: if check not visited, then append last non-wall pos to queue
r = len(maze)
c = len(maze[0])
seen = [[False]*c for _ in range(r)]
q = collections.deque()
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
q.append((start[0],start[1]))
seen[start[0]][start[1]] = True
while q :
x,y = q.popleft()
if x == destination[0] and y == destination[1]:
return True
for d in dirs:
xx = x + d[0]
yy = y + d[1]
# optimization: xx =x ; yy = y
# while 0 <= xx+d[0]< r and 0 <= yy+d[1] < c and maze[xx+d[0]][yy+d[1]] == 0:
while 0 <= xx < r and 0 <= yy < c and maze[xx][yy] == 0:
xx += d[0]
yy += d[1]
# last valid cell before hitting the wall
xx -= d[0]
yy -= d[1]
if seen[xx][yy] == False:
q.append((xx,yy))
seen[xx][yy] = True
return False