The Maze
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix · Graph
Problem
A ball sits in a maze given as an m x n grid maze, where 0 is an empty cell and 1 is a wall. Everything outside the grid also acts as a wall.
The ball can be pushed up, down, left or right, and once pushed it keeps rolling until the next cell is a wall. Only when it has stopped can you choose its next direction.
Given the ball’s start = [row, col] and a destination = [row, col], return true if the ball can come to rest exactly at the destination. Rolling over 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: true
The ball can stop at [0,3], [1,3], [1,0], [2,0], [2,2], [4,2] and finally [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: false
The ball can pass through [3,2] but never stops there.
Constraints
- m == len(maze), n == len(maze[i])
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1
- start and destination are different empty cells inside the maze
Approaches
- Grow the set of stops in rounds — time O((mn)² · (m + n)), space O(mn)
Follow-up
What if you wanted the shortest rolling distance (cells travelled) to stop at the destination? Rolls have different lengths, so BFS order no longer gives the shortest path: run Dijkstra’s algorithm over the same stops with a heap keyed by distance. And to report the lexicographically smallest sequence of moves that drops the ball into a hole, add the path string to the heap key.
Related problems
Start free on Cariara · Coding problems · System design studio
