The Maze II
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Graph · Heap (Priority Queue) · Matrix · Shortest Path
Problem
A ball is in a maze maze of 0s (empty) and 1s (walls); the border of the grid behaves like a wall. Pushed in one of the four directions, the ball rolls until the next cell is a wall and stops there, after which you may push it again.
Given start and destination, return the shortest distance for the ball to stop at the destination, or -1 if that is impossible. Distance is the number of empty cells the ball rolls over, counting the destination but not the starting cell. Rolling through the destination without stopping there does not count.
Examples
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: 12
Roll left, down, left, down, right, down, right: 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12 cells is the shortest way to stop at [4,4].
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] Output: -1
The ball can roll through [3,2] but never stops on it, so the answer is -1.
Input: maze = [[0,0,0]], start = [0,0], destination = [0,2] Output: 2
One push to the right rolls two cells to the far wall.
Constraints
- m == maze.length, n == maze[i].length
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1
- start and destination are empty cells and are different
Approaches
- Baseline: queue with re-relaxation — time worse than Dijkstra in the worst case, space O(m·n)
Follow-up
The graph is implicit: nodes are stopping cells and edges are rolls, found on demand. The use cases keep the rolling rule and ask for the fewest pushes (equal weights, so plain BFS) and for how many cells the ball can stop at at all.
Related problems
Start free on Cariara · Coding problems · System design studio
