383. The Maze
A ball is dropped into an m × n grid maze, where 0 marks an open cell and 1 marks a wall. The ball is frictionless: when you push it up, down, left, or right, it keeps rolling in that straight line and only comes to rest when the next cell would be a wall or the edge of the grid. From a resting position you may push it again in any direction.
Your function receives the grid maze, the ball's starting cell start = [row, col], and a target cell destination = [row, col] (both open, 0-based). Return true if some sequence of pushes can bring the ball to rest exactly on destination, and false otherwise.
Rolling through the destination does not count — the ball has to stop there.
Example 1:
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
Explanation: One winning sequence of pushes: left, down, left, down, right, down, right. Each push rolls the ball until a wall or the border stops it, and the final roll ends exactly on the destination.
Example 2:
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
Explanation: The ball can roll straight through cell (3, 2) while travelling down column 2, but no wall ever stops it on that cell, so it can never rest there.
Constraints:
- 1 ≤ m, n ≤ 100
- maze[i][j] is 0 or 1
- start and destination are open cells inside the grid
- start and destination may be the same cell
Hints:
The ball cannot stop on every open cell. Instead of moving one square at a time, think about which cells the ball can actually come to rest on.
From any resting cell, rolling in one of the four directions deterministically ends at another resting cell. Those resting cells are the nodes of a graph and each full roll is an edge — now it is ordinary BFS/DFS with a visited set.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
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]
Expected output: true