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
- This is Dijkstra on the stopping positions, since each roll has a length.
- The cost of rolling from
(r, c)in a direction is the number of cells travelled. - Pop the closest stopping position, and if it is the destination, return its distance.
- 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.