Minimum Moves to Reach Target with Rotations
candidate master · 1395 · lc hard +32 · verified · 51.9% accepted · 288 likes · top 41%
Description
In an n*n grid, a two-cell snake starts horizontally at (0, 0) and (0, 1). Cells with 0 are passable; cells with 1 are blocked. The goal is to bring the snake's tail to (n-1, n-2) and head to (n-1, n-1).
Each move, the snake can:
- Slide one cell to the right (keeping its orientation), if all destination cells are unblocked.
- Slide one cell downward (keeping its orientation), if all destination cells are unblocked.
- Rotate clockwise (horizontal to vertical) if the two cells directly below it are both free: the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
- Rotate counterclockwise (vertical to horizontal) if the two cells directly to its right are both free: the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).
Return the minimum number of moves to reach the target, or -1 if impossible.
Example 1:
Example 2:
Code