Rolling Ball Maze Reachability
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Rolling Ball Maze Reachability
Implement `has_rolling_path(maze: list[list[int]], start: list[int], destination: list[int]) -> bool`.
The maze is a rectangular grid where `0` is open and `1` is a wall. A ball placed at `start` may choose one of the four cardinal directions, but once moving it continues until the next step would hit a wall or leave the grid. It may choose a new direction only after stopping. Return whether the ball can stop exactly at `destination`.
### Input Domain
- `maze` has `m` rows and `n` columns, where `1 <= m, n <= 100`.
- Every cell is `0` or `1`.
- `start` and `destination` are two-element `[row, column]` lists naming open cells.
- The input maze is not modified.
### Output Rules
- Return `true` only if some sequence of rolls ends with the ball stopped at `destination`.
- Passing through the destination without stopping does not count.
### Constraints
- Explore at most the set of stopping cells; repeated visits to the same stop need not be expanded.
- Output is a single Boolean, so tie semantics are not applicable.
### Examples
#### 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`
#### 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`
```hint Treat stops as states
A useful search state is a cell where the ball has stopped, not every open cell it crosses while rolling.
```
Quick Answer: Solve a rolling-ball maze reachability problem where direction changes are allowed only at stopping cells.