TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- Check every location the ball can end up at, which means checking the ball location after slide up, down, left, and right, respectively.
- Then, after each position the ball can be in, check if that position is the goal.
- Return true immediately if that is the case. Otherwise, continue simulating every position, and backtrack for every position.
- Also note that there is no wall padding (that is fake in that going out of bounds constitutes hitting a wall).
Complexity
Runtime
since you have to every single element in the grid in the worst case, but the seen set ensures you only traverse once.
Space
due to the visited set holding every location.
Code
Using Helper Move Function
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
visited = set()
def move(x, y, dx, dy):
while 0 <= x + dx < m and 0 <= y + dy < n and maze[x + dx][y + dy] == 0:
x += dx
y += dy
return x, y
def dfs(r, c):
if [r, c] == destination:
return True
if (r, c) in visited:
return False
visited.add((r, c))
for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_r, new_c = move(r, c, dx, dy)
if dfs(new_r, new_c):
return True
return False
return dfs(start[0], start[1])Faster Solution but less Elegant
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
seen = set()
def dfs(r, c):
if destination[0] == r and destination[1] == c:
return True
if (r, c) in seen:
return False
seen.add((r, c))
# Go down until hit wall
i, j = r, c
while 0 <= i + 1 < m and maze[i + 1][j] == 0:
i += 1
if dfs(i, j):
return True
# Go up until hit wall
i, j = r, c
while 0 <= i - 1 < m and maze[i - 1][j] == 0:
i -= 1
if dfs(i, j):
return True
# Go left until hit wall
i, j = r, c
while 0 <= j - 1 < n and maze[i][j - 1] == 0:
j -= 1
if dfs(i, j):
return True
# Go right until hit wall
i, j = r, c
while 0 <= j + 1 < n and maze[i][j + 1] == 0:
j += 1
if dfs(i, j):
return True
return False
return dfs(start[0], start[1])Notes
Cards
START Basic Front: The Maze Back: Check every location the ball can end up at
END