The Maze III
Hard · Graphs · Array · String · Depth-First Search · Breadth-First Search · Graph · Heap (Priority Queue) · Matrix · Shortest Path
Problem
A ball sits in a maze maze of 0s (empty) and 1s (walls); the border of the grid also acts as a wall. Pushed up ('u'), down ('d'), left ('l') or right ('r'), the ball keeps rolling until a wall stops it. The maze also has a hole at hole: if the ball rolls onto the hole, it falls in at once, even in the middle of a roll.
Given the ball's position ball and the hole, return the moves, as a string of direction letters, that drop the ball into the hole over the shortest distance: the number of empty cells travelled, not counting the start and counting the hole. If several move strings share the shortest distance, return the lexicographically smallest. If the hole cannot be reached, return "impossible".
Examples
Input: maze = [[0,0,0,0],[0,1,0,0],[0,0,0,1]], ball = [2,0], hole = [0,2] Output: "ru"
Both "ru" (right to [2,2], then up into the hole) and "ur" travel 4 cells, and "ru" is lexicographically smaller.
Input: maze = [[0,0,0],[0,0,0]], ball = [0,0], hole = [1,1] Output: "dr"
Down stops at [1,0], then right drops the ball in after 2 cells in all. Rolling right first carries the ball past column 1 on the top row.
Input: maze = [[0,1,0]], ball = [0,0], hole = [0,2] Output: "impossible"
The wall in the middle blocks the only way across.
Constraints
- m == len(maze), n == len(maze[i])
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1
- ball and hole are empty cells and are different
- The maze has at least 2 empty cells
Approaches
- Baseline: relax with a plain queue until nothing improves — time O((m · n)² · (m + n)), space O(m · n · (m + n))
Follow-up
Why is the tie-break safe inside Dijkstra? Two different move strings that reach the same cell with the same distance first differ at some letter (neither can be a prefix of the other, since every extra move adds distance), so adding the same letters to both keeps their order. If pushes could roll zero cells, that argument would fail.
Related problems
Start free on Cariara · Coding problems · System design studio
