Inverted Gravity Grid Traversal
You are given an $R \times C$ grid containing empty spaces (.), solid walls (#), a starting position (S), and a target position (T).
You start at cell S with gravity pulling DOWN and $K$ gravity flips available. The outer perimeter beyond the grid boundaries (above row $0$, below row $R-1$, left of column $0$, and right of column $C-1$) behaves as solid walls.
Movement Rules & Physics
- Gravity States: Gravity is either DOWN or UP.
- Anchoring: You are considered anchored if:
- Gravity is DOWN and the cell directly below you is a solid wall
#(or row index $R$, the bottom boundary). - Gravity is UP and the cell directly above you is a solid wall
#(or row index $-1$, the top boundary).
- Gravity is DOWN and the cell directly below you is a solid wall
- Actions:
- Flip Gravity: At any time, if you have remaining flips ($k > 0$), you can toggle gravity between DOWN and UP. This uses $1$ flip and takes 0 time units. Anchoring status updates immediately.
- Walk Left / Right: If you are anchored, you may walk $1$ cell left or $1$ cell right into an adjacent non-wall cell. This takes 1 time unit.
- Fall / Float (Auto-move): If you are NOT anchored, you cannot walk left or right. You MUST move $1$ cell in the current gravity direction (DOWN or UP) into a non-wall cell. This takes 1 time unit.
Reaching the target cell T (whether by walking, falling, or floating onto it) immediately finishes the traversal. Determine the minimum total time units needed to reach T. If T cannot be reached, return -1.
[ "[\"#.#\", \".S.\", \"#.#\", \".T.\", \"###\"]", "0" ]
Explanation. Start at (1,1) with gravity DOWN. Since (2,1) is empty space, you are not anchored and fall DOWN to (2,1) (1 time unit) and then to (3,1) where 'T' is located (1 time unit). Total time taken is 2.
[ "[\"...\", \"S.T\", \"...\"]", "1" ]
Explanation. Start at (1,0) with gravity DOWN. Falling down to row 2 takes 1 step. Walking right on the bottom boundary to (2,2) takes 2 steps. Flipping gravity to UP takes 0 time, then floating UP to (1,2) ('T') takes 1 step. Total time is 4 steps.
[ "[\"...\", \".#.\", \"S#T\", \"###\"]", "2" ]
Explanation. Start at (2,0) anchored on the bottom wall. Flip gravity to UP (0 time), float UP to (0,0) (2 steps), walk right along the top border to (0,2) (2 steps), flip gravity to DOWN (0 time), and fall DOWN to (2,2) ('T') (2 steps). Total time is 6 steps.
[ "[\"S#T\"]", "5" ]
Explanation. Start is bounded by walls and horizontal movement is blocked by the middle solid cell '#'. The target 'T' is unreachable.
[ "[\"#.#\", \"#S#\", \"#.#\", \"#.#\", \"#T#\"]", "0" ]
Explanation. Start at (1,1) with gravity DOWN. Unanchored, you fall straight through (2,1) and (3,1) until landing on 'T' at (4,1) in 3 steps.
Follow-up: Can you solve this using 0-1 BFS in $O(R \cdot C \cdot K)$ time complexity?
- $1 \le R, C \le 100$ - $0 \le K \le 50$ - `grid` consists of characters '.', '#', 'S', and 'T'. - There is exactly one 'S' and exactly one 'T' in the grid.
- Views
- 2