Minimum Moves to Reach Target with Rotations
01 · Problem
A snake occupies two adjacent cells in an n x n grid, where 0 is an empty cell and 1 is blocked. It starts horizontally, covering (0, 0) and (0, 1), and wants to end horizontally covering (n - 1, n - 2) and (n - 1, n - 1).
Each move is one of:
- Move right: shift both cells one column right, if both destination cells are empty.
- Move down: shift both cells one row down, if both destination cells are empty.
- Rotate clockwise: when horizontal at
(r, c)and(r, c + 1), become vertical at(r, c)and(r + 1, c); requires(r + 1, c)and(r + 1, c + 1)to be empty. - Rotate counterclockwise: when vertical at
(r, c)and(r + 1, c), become horizontal at(r, c)and(r, c + 1); requires(r, c + 1)and(r + 1, c + 1)to be empty.
The snake may never leave the grid. Return the minimum number of moves to reach the target position, or -1 if it cannot be reached.
02 · Examples
grid = [[0,0,0],[0,0,0],[0,0,0]]
3
Move right to cover (0,1)-(0,2), then move down twice to reach (2,1)-(2,2).
grid = [[0,0,0,0],[1,1,0,0],[0,0,0,0],[0,1,0,0]]
5
Move right twice to (0,2)-(0,3), then move down three times through the empty rightmost two columns to (3,2)-(3,3).
grid = [[0,0,1],[0,1,0],[0,0,0]]
-1
The snake cannot move right because (0,2) is blocked, cannot move down because (1,1) is blocked, and cannot rotate for the same reason, so it is stuck.
03 · Constraints
- 012 <= n <= 100
- 02grid[i][j] is 0 or 1
- 03The starting cells and the target cells are always empty
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.