The maze: a rolling ball, its shortest roll and a hole

A ball sits in a maze, a grid where 0 is open and 1 is a wall. You push it up, down, left or right, and it keeps rolling until the next cell is a wall or off the grid; it can only stop there, never part way. Answer four questions about the same maze, one method each.

Part 1: Can the ball stop at the destination?

• can_stop(maze: list[list[int]], start: tuple[int, int], dest: tuple[int, int]) -> bool — rolling through dest doesn't count; the ball must come to rest on it.

Part 2: Shortest distance to stop at the destination

• shortest_distance(maze, start, dest) -> int — the fewest cells rolled over in total (each roll counts the cells it moves, not 1), or -1.

Part 3: Fall into a hole

A hole cell is added. The ball drops into it the moment it rolls onto it, even mid-roll. Moves are written d, l, r, u.

• find_hole_path(maze, ball, hole) -> str — among the paths with the shortest distance, the lexicographically smallest move string; "impossible" when the hole can't be reached.

Part 4: Many queries on one maze

The maze stays the same and you get many (start, dest) queries for Part 2. Explain, or build, how you would reuse work across them.

Example

maze = [[0, 0, 0, 1],
        [1, 1, 0, 0],
        [0, 0, 0, 1],
        [0, 1, 0, 0]]

can_stop(maze, (0, 0), (3, 3))           ->  True
shortest_distance(maze, (0, 0), (3, 3))  ->  6    # r to (0,2): 2, d to (3,2): 3, r to (3,3): 1
can_stop(maze, (0, 0), (2, 1))           ->  False   # the ball only rolls through (2,1)
shortest_distance(maze, (0, 0), (2, 1))  ->  -1
find_hole_path(maze, (0, 0), (2, 2))     ->  "rd"    # the ball drops in on its way down
find_hole_path(maze, (0, 0), (2, 1))     ->  "impossible"

Constraints

• 1 <= rows, cols <= 100; start, dest, ball and hole are open cells.

Clarifying questions

• Does the distance count cells rolled over, or the number of pushes?
• Is the start itself a valid answer when start == dest?
• Can the ball be pushed in a direction where it can't move at all?
• In Part 3, does the ball fall in only when it stops on the hole, or as soon as it passes over it?
• For Part 4, how many queries, and do they share start cells?

What a strong answer covers

• The graph is over stopping cells, not every cell: from each stop, simulate the four rolls to find the next stops. BFS or DFS with a visited set answers Part 1 in O(m * n * (m + n)).
• Rolls have different lengths, so plain BFS by pushes is wrong for Part 2; Dijkstra on the stopping cells, with the roll length as the edge weight.
• Part 3: Dijkstra ordered by (distance, path string), checking for the hole on every cell of a roll and ending the roll there.
• Part 4: precompute, for every open cell and direction, where the roll ends and how long it is; group queries by start and run Dijkstra once per distinct start.
• Tests: start equals destination, a destination the ball passes but can't stop on, a single open cell, a hole on the first roll.

Follow-ups

• Return the actual sequence of pushes for Part 2.
• Some cells are ice, where the ball keeps going, and some are sand, where it stops at once.
• The maze changes between queries in Part 4: one wall is added or removed at a time.