You are provided a maze of size m X n. Each cell can be either empty ('.') or a wall ('X'). A ball is initially placed at the start point ('s') and must reach the end point ('e'). There is exactly one 's' and 'e' in the maze.
The ball moves using gravity by rotating the maze 90 degrees to the left (counter-clockwise) or to the right (clockwise). Your goal is to find C, the number of cells the ball passes through while moving from start point to end point (both excluded).
Rules:
1. The ball must come to rest on 'e'. Merely passing through 'e' during motion does not complete the task.
2. Gravity initially acts downward. Before the first rotation, the ball falls downward until it hits a wall or falls off the maze.
3. Find a valid solution that uses the minimum number of maze rotations.
4. Left rotation (counter-clockwise) has priority over right rotation (clockwise) if multiple solutions use the same minimum number of rotations.
5. After every rotation, the ball slides continuously in the direction of gravity until the next cell is a wall. It is possible for the ball to fall off the grid (invalid path).
5 5 s.... XXXX. ..... .XXXX ....e
8
The ball falls downward, rests, and with minimal rotations rolls towards cell 'e', resting exactly on 'e' after traversing 8 intermediate cells.
1. Represent gravity direction as d in {0: Down, 1: Right, 2: Up, 3: Left}. 2. A counter-clockwise rotation changes gravity from d to (d + 1) % 4. Clockwise rotation changes gravity to (d + 3) % 4. 3. Simulate sliding from (r, c) along direction d: return {final_r, final_c, steps, stopped_on_e, fell_off}. 4. Run a BFS over states (resting_r, resting_c, gravity_dir) to find the path with minimum rotations. 5. Priority queue or tiered BFS prioritizes minimum rotations, then counter-clockwise turns first.