⚡Flashcard Drill➔
NeetCode #611LC-505MediumGraphsNC Algo100
← Back to All Problems

#611 · #505 · The Maze II(迷宫 II)

📌 Problem Statement & Constraints

A ball rolls in a maze until it hits a wall. Given start and destination, return the shortest distance (number of empty cells passed, excluding the start) for the ball to stop at the destination, or -1. Constraints: 1 <= m, n <= 100.

💡 Core Algorithmic Approaches

  1. This is Dijkstra on the stopping positions, since each roll has a length.
  2. The cost of rolling from (r, c) in a direction is the number of cells travelled.
  3. Pop the closest stopping position, and if it is the destination, return its distance.
  4. Unlike The Maze I, the distance matters, so a plain BFS over stopping positions is not enough.

💻 Benchmark Python3 Implementation

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        import heapq
        m, n = len(maze), len(maze[0])
        dist = {}
        h = [(0, start[0], start[1])]
        while h:
            d, r, c = heapq.heappop(h)
            if (r, c) in dist:
                continue                   # already settled with a smaller distance
            dist[(r, c)] = d
            if [r, c] == destination:
                return d
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc, steps = r, c, 0
                while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
                    nr += dr
                    nc += dc
                    steps += 1
                if (nr, nc) not in dist:
                    heapq.heappush(h, (d + steps, nr, nc))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n * (m + n) log(m * n)): each stopping cell rolls four times.
💾 Space Complexity
O(m * n) for the distance map and the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Using a plain BFS: the roll lengths differ, so a queue does not yield the shortest distance.
  • Marking visited when pushing instead of when popping: a shorter path to the same cell could be missed.
  • Counting the start cell in the distance: the distance counts the cells the ball rolls through, excluding the start.
  • Stopping the roll early: the ball must roll until blocked.
⚡
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