490. The Maze
Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 52.9%
Problem Breakdown
We are given a grid representing a maze where 0 is an empty space and 1 is a wall. The core constraint here isn’t just movement; it’s inertia. A ball rolls in one of four directions (up, down, left, right) but cannot stop arbitrarily—it only stops when it hits a boundary or another cell containing a wall (1).
Inputs:
maze: 2D list of integers.start:[row, col]coordinates.destination:[row, col]coordinates.
Output: Boolean indicating if the ball can stop exactly at the destination cell. Passing through it while rolling does not count (as per Example 2).
Implicit Constraints & Edge Cases:
- The grid boundaries act as implicit walls; we must check bounds before moving out of range.
- Start and Destination are guaranteed to be empty spaces (
0). - We cannot stop at the destination if it is not a valid stopping point (i.e., there isn’t a wall/boundary immediately adjacent in that direction).
Intuition
A naive approach might try BFS/DFS on every cell (r, c) assuming we can step to any neighbor. This fails because movement isn’t discrete steps; moving “down” from A doesn’t mean landing at B (adjacent), but rather rolling until a wall is hit. If we treat each grid cell as a node in our graph, the edges are defined by these roll mechanics.
If we don’t track visited states correctly, we risk infinite loops: e.g., ball rolls Left to stop, then immediately rolls Right back to start. We need to ensure that once we process a specific stopping position (r, c), we mark it as visited so the algorithm doesn’t re-explore paths from there unnecessarily.
Since this is an unweighted reachability problem (we just want any path), Breadth-First Search (BFS) or Depth-First Search (DFS) are both valid choices. I’ll use BFS with a queue to systematically explore reachable stopping points level by level, which avoids recursion depth issues in Python and handles the state space robustly.
Approach
- Initialization: Create a
visitedset/matrix to track cells where the ball has successfully stopped. Initialize a Queue (deque) with thestartposition. Add start to visited immediately if we treat it as processed, or handle logic carefully so we don’t re-add it. Actually, standard practice: add start to queue and mark visited when popped? No, better to mark visited upon generation of new states to prevent duplicates in the queue. - Traversal: While the Queue is not empty:
- Pop current position
(r, c).
- Pop current position
- Rolling Logic: For each direction (up/down/left/right):
- Simulate rolling by incrementally updating
nr,ncin that direction while checking bounds and ensuringmaze[nr][nc] == 0. - Stop when the next cell is a wall or out of bounds. The current
(nr, nc)becomes the new stopping point.
- Simulate rolling by incrementally updating
- Check Destination: If this new stopping point matches
destination, returnTrueimmediately. Note: We must check if we stopped at destination; passing through it during roll doesn’t count unless that cell is a valid stop (which implies hitting a wall next to it). The rolling loop naturally handles the “stop” condition, so checking equality after the loop ensures we only consider stopping points. - State Management: If
(nr, nc)hasn’t been visited yet:- Mark as visited.
- Add to Queue for further exploration from this new stop point.
- Termination: If queue empties without reaching destination, return
False.
Complexity Analysis
- Time Complexity: . Although rolling takes time proportional to the distance moved, each cell is added to the Queue at most once (due to the visited set). The total number of valid stopping points across all directions is bounded by the grid size. In practice, we visit every reachable empty space as a potential stop point exactly once per direction logic amortized over the traversal.
- Space Complexity: for the
visitedarray and the Queue in worst case (filling up with all cells).
Solution
from collections import deque
from typing import List
def hasPath(maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
# Directions: up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
queue = deque([tuple(start)])
visited.add(tuple(start))
while queue:
r, c = queue.popleft()
# If we are at the destination and stopped there
if [r, c] == destination:
return True
for dr, dc in directions:
nr, nc = r + dr, c + dc
# Roll until hitting a wall or boundary
while 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == 0:
nr += dr
nc += dc
# Backtrack one step because the loop stopped at the cell AFTER the last valid empty space (which is effectively a wall/boundary)
# Wait, logic check:
# The while condition checks if next is valid. If invalid, we exit loop.
# So nr, nc are currently pointing to the obstacle/wall/outside? No.
# Let's re-verify rolling logic inside code block below for precision.
# Correct Rolling Logic Implementation:
curr_r, curr_c = r + dr, c + dc
while 0 <= curr_r < m and 0 <= curr_c < n and maze[curr_r][curr_c] == 0:
curr_r += dr
curr_c += dc
# Now (curr_r, curr_c) is the wall/boundary. The stopping point is one step back?
# No, usually we check bounds first then move. If valid empty space exists at next pos, keep moving.
# Let's refine logic in code block to ensure correctness:
pass
return False
# Re-writing solution cleanly inside the final block below with correct rolling mechanics
Self-Correction on Rolling Logic for Code:
The loop while 0 <= nr < m ... checks if we can move. If valid, increment and continue. When it breaks, (nr+dr) is invalid (wall/boundary). So the last valid position was (curr_r - dr).
Actually simpler: Start at current pos + direction step. While next cell in that dir is empty (0), keep moving forward. The loop exits when we hit a wall or boundary. At exit, nr, nc points to the obstacle/boundary (or out of bounds). We need to subtract one step back?
Wait, if I am at (r,c) and move down:
-
Check
(r+dr). If 0, update pos =(r+dr). Increment again. -
Repeat until
maze[pos]is 1 or out of bounds. -
The position before the wall/boundary is where we stop.
-
So if loop exits because condition failed (wall/out), current
nr, ncholds the invalid index? No, usually logic:nr = r + dr while 0 <= nr < m and maze[nr][nc] == 0: # Wait need to check bounds first or inside loop properly nr += dr nc += dcIf I do
nr, ncas the next cell. While valid empty space at(nr, nc), move there and continue? No, that’s confusing.Correct Logic: Start with
curr_r = r + dr. Check if0 <= curr_r < mANDmaze[curr_r][c+dc] == 0. If true: updater=curr_r, increment again. Actually, simpler pattern used in standard solutions:nr, nc = r + dr, c + dc while 0 <= nr < m and maze[nr][nc] == 0: # Wait this checks current cell? nr += dr nc += dcIf I start
nrat neighbor. While valid empty space (check bounds AND value), move forward. When loop breaks,nr,ncis the wall/boundary index or out of range. The actual stop position is(nr - dr, nc - dc).Wait, let’s trace: Start at 0,4. Move Left (-1). Next (0,3). If empty, move to (0,2)… until hit wall. Suppose grid row
... [0] ...and next is1. Loop checks(nr)which is valid index but value is1. Condition fails immediately? No, usually check bounds first then maze content.Refined Logic:
nr = r + dr nc = c + dc while 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == 0: nr += dr nc += dc # Now (nr, nc) is the wall/boundary. The stop position is (nr-dr, nc-dc).Wait, if
mazeat(nr)was1, loop doesn’t run? No, we need to check bounds first then value. If I use short-circuit evaluation:0 <= nr < m and maze[nr][nc] == 0. If out of bounds, it stops. So after loop,nris the index of wall/boundary (or invalid). The ball stopped at(nr-dr, nc-dc).Actually, simpler: Just update position inside a while loop where we check if next step is valid empty space? No, standard way:
nr = r + dr nc = c + dc # Move as long as the cell in that direction is 0 (empty) and within bounds. # Wait, usually logic checks current position validity before moving further? # Let's stick to standard pattern: curr_r, curr_c = r + dr, c + dc while 0 <= curr_r < m and maze[curr_r][curr_c] == 0: curr_r += dr curr_c += dc stop_pos = (curr_r - dr, curr_c - dc)Wait, if
mazeat(r+dr)is wall. Loop condition fails immediately? No, loop checks bounds then value. If it’s a wall (1), loop doesn’t execute body.stop_posbecomes invalid relative to start?Let’s write the code carefully in the final block.
## Edge Cases Handled
* **Start equals Destination**: The problem states they are not initially same, but logic handles it (queue starts with start; if destination is checked immediately or during roll). If `start` was dest, loop check `[r,c] == destination` catches it before rolling.
* **Destination unreachable due to walls**: BFS exhausts all reachable stopping points without finding target, returns False.
* **Passing through Destination**: The code only checks equality when the ball *stops*. If we roll over `destination`, `(nr, nc)` will be a wall/boundary adjacent to it (or beyond), so `[r,c]` won't match destination unless that specific cell is where inertia stops us.
* **Boundary Walls**: Bounds check (`0 <= nr < m`) handles implicit walls at grid edges.
```python
from collections import deque
from typing import List
def hasPath(maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
if not maze or not maze[0]:
return False
rows, cols = len(maze), len(maze[0])
# Directions: Up, Down, Left, Right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = set()
queue = deque([tuple(start)])
visited.add(tuple(start))
while queue:
r, c = queue.popleft()
# Check if current stopping point is the destination
if [r, c] == destination:
return True
for dr, dc in directions:
nr, nc = r + dr, c + dc
# Roll until we hit a wall or boundary.
# We check bounds and empty space (0). If valid, keep moving forward.
while 0 <= nr < rows and maze[nr][nc] == 0:
nr += dr
nc += dc
# The loop exits when next cell is out of bounds or a wall (1).
# So the ball stops at one step back from where we exited.
stop_r, stop_c = nr - dr, nc - dc
if [stop_r, stop_c] == destination:
return True
if tuple((stop_r, stop_c)) not in visited:
visited.add(tuple((stop_r, stop_c)))
queue.append((stop_r, stop_c))
return False