⚡Flashcard Drill➔
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

  1. BFS over the stopping positions, not every cell the ball passes through.
  2. From a stopping position, roll in each of the four directions until the next cell is a wall or out of bounds.
  3. The resulting cell is the new stopping position; enqueue it if unseen.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems