This looks like a standard shortest path problem, but the ball does not stop at every cell. Once it starts rolling in a direction, it keeps going until it hits a wall. Only then does it stop, and only at a stopping position can it change direction.

So the search is not over a grid where every cell is a node. The nodes are the positions where the ball can come to rest (the cell right before a wall), the edges are the rolling paths between those stopping positions, and each edge weight is the number of cells the ball travels along that path.

This is a weighted shortest path problem on an implicit graph. The ball rolls a variable distance in each direction, so edges have different weights. Plain BFS only finds shortest paths when every edge has weight 1, so it does not apply directly here. The two approaches that do are Dijkstra's algorithm and a BFS variant that keeps updating distances.

Key Constraints:

Intuition

Treat the maze as a graph and explore it with a queue. From the start position, roll the ball in all four directions. Each time it stops, record the distance traveled to reach that stopping point. Whenever a shorter distance to an already-seen position is found, update it and re-enqueue that position so the improvement propagates onward.

This is BFS over a weighted graph. In standard BFS, the first time a node is reached gives its shortest distance, but that holds only when every edge has weight 1. Here the ball rolls different distances, so a node first reached by a long roll might later be reachable by a shorter combination of rolls. Re-enqueuing on every improvement handles that case, at the cost of processing some nodes more than once.

Algorithm

Visualization and Code

This is correct but can process the same node several times before its distance settles. Processing positions in order of their known distance, smallest first, finalizes each node exactly once. That ordering is Dijkstra's algorithm.

Intuition

The BFS approach does not process nodes in distance order, so a node can be processed many times before its distance is final. A min-heap fixes this by always extracting the unfinished node with the smallest tentative distance.

When a node is popped from the min-heap, its recorded distance is already its shortest. Any other path to it would pass through a node still in the heap, and every such node has an equal or larger distance, so it cannot produce a shorter total. Each node is therefore finalized once.

Algorithm

Visualization and Code