The Maze III
01 · Problem
A ball sits in a maze given as an m x n grid, where 0 is an open cell and 1 is a wall. The area outside the grid acts as a wall too. The ball moves by rolling up (u), down (d), left (l) or right (r): once pushed it keeps rolling until the next cell would be a wall, and only then may you choose a new direction. There is a hole in the maze: if the ball rolls over the hole cell it drops in immediately, even mid-roll.
Given the ball's starting cell ball = [row, col] and the hole = [row, col], return the instruction string (made of 'u', 'd', 'l', 'r') that drops the ball into the hole while travelling the fewest cells. Distance is the number of empty cells moved over, not counting the start cell. If several instruction strings achieve the same shortest distance, return the lexicographically smallest one. If the hole cannot be reached, return "impossible".
02 · Examples
maze = [[0,0,0],[0,1,0],[0,0,0]], ball = [2,2], hole = [0,0]
"lu"
Both "lu" (left 2 cells, then up 2 cells) and "ul" (up 2, then left 2) travel 4 cells. They tie, so the lexicographically smaller string "lu" is returned.
maze = [[0,0,0,0,0],[0,1,0,1,0],[0,0,0,0,0]], ball = [0,4], hole = [2,1]
"dl"
Roll down 2 cells to (2,4), then roll left; the ball passes (2,3) and (2,2) and drops into the hole at (2,1) for a total distance of 5. Every other route is longer.
maze = [[0,0,0,0],[1,1,0,1],[0,0,0,0]], ball = [2,0], hole = [0,1]
"impossible"
Rolling right sends the ball all the way to (2,3), where up is a wall; it can never stop under the opening at column 2, so it cannot reach the top row.
03 · Constraints
- 01m == maze.length, n == maze[i].length
- 021 <= m, n <= 100
- 03maze[i][j] is 0 or 1
- 04ball and hole are both empty cells and ball != hole
04 · Optimal complexity
- Time
- O(m * n * max(m, n) * log(m * n))
- Space
- O(m * n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.