NeetCode #610LC-490MediumGraphsNC Algo100
← Back to All Problems#610 · #490 · The Maze(迷宫)
📌 Problem Statement & Constraints
A ball rolls in a maze of
0 (empty) and 1 (wall) cells until it hits a wall. Given start and destination, return whether the ball can stop at the destination. Constraints: 1 <= m, n <= 100, start and destination are distinct empty cells.💡 Core Algorithmic Approaches
- BFS over the stopping positions, not every cell the ball passes through.
- From a stopping position, roll in each of the four directions until the next cell is a wall or out of bounds.
- The resulting cell is the new stopping position; enqueue it if unseen.
- The ball stops only when blocked, which is why the state space is the stopping cells.
💻 Benchmark Python3 Implementation
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
from collections import deque
m, n = len(maze), len(maze[0])
seen = {tuple(start)}
q = deque([tuple(start)])
while q:
r, c = q.popleft()
if [r, c] == destination:
return True
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r, c
# roll until blocked
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
nr += dr
nc += dc
if (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc))
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n * (m + n)): each stopping cell rolls in four directions, each up to O(m + n) long.
💾 Space Complexity
O(m * n) for the visited set and the queue.
⚠️ Interview Pitfalls & Follow-ups
- Enqueuing every cell the ball passes through: only the stopping positions matter.
- Stopping one cell too early or late: the roll must continue while the next cell is empty.
- Forgetting the bounds check in the roll loop: the ball can leave the maze.
- Requiring the ball to be able to stop exactly at the destination: the destination is a valid stopping cell, and the BFS finds it if reachable.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.