Minimum Moves to Reach Target with Rotations
Problem
In an n x n grid, a snake occupies two cells. It starts horizontal at the top-left, covering cells (0,0) and (0,1). Each minute the snake can move right, move down, rotate clockwise (if horizontal), or rotate counter-clockwise (if vertical), as long as the cells it needs are empty (0) and not blocked (1). Return the minimum number of moves to reach the target where the snake occupies (n-1, n-2) and (n-1, n-1); return -1 if impossible.
grid = [[0,0,0,0,0,1],[1,1,0,0,1,0],[0,0,0,0,1,1],[0,0,1,0,1,0],[0,1,1,0,0,0],[0,1,1,0,0,0]]11from collections import deque
def minimum_moves(grid):
n = len(grid)
# state = (r, c, h): snake head at (r, c); h=0 horizontal, h=1 vertical
start = (0, 0, 0)
target = (n - 1, n - 2, 0)
seen = {start}
q = deque([(start, 0)])
while q:
(r, c, h), d = q.popleft()
if (r, c, h) == target:
return d
nxt = []
if h == 0: # horizontal: tail at (r, c+1)
if c + 2 < n and grid[r][c + 2] == 0:
nxt.append((r, c + 1, 0)) # move right
if r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c + 1] == 0:
nxt.append((r + 1, c, 0)) # move down
nxt.append((r, c, 1)) # rotate clockwise
else: # vertical: tail at (r+1, c)
if r + 2 < n and grid[r + 2][c] == 0:
nxt.append((r + 1, c, 1)) # move down
if c + 1 < n and grid[r][c + 1] == 0 and grid[r + 1][c + 1] == 0:
nxt.append((r, c + 1, 1)) # move right
nxt.append((r, c, 0)) # rotate counter-clockwise
for s in nxt:
if s not in seen:
seen.add(s)
q.append((s, d + 1))
return -1function minimumMoves(grid) {
const n = grid.length;
const key = (r, c, h) => r * n * 2 + c * 2 + h;
const start = [0, 0, 0];
const seen = new Set([key(0, 0, 0)]);
let q = [[start, 0]];
while (q.length) {
const next = [];
for (const [[r, c, h], d] of q) {
if (r === n - 1 && c === n - 2 && h === 0) return d;
const cand = [];
if (h === 0) {
if (c + 2 < n && grid[r][c + 2] === 0) cand.push([r, c + 1, 0]);
if (r + 1 < n && grid[r + 1][c] === 0 && grid[r + 1][c + 1] === 0) {
cand.push([r + 1, c, 0]); cand.push([r, c, 1]);
}
} else {
if (r + 2 < n && grid[r + 2][c] === 0) cand.push([r + 1, c, 1]);
if (c + 1 < n && grid[r][c + 1] === 0 && grid[r + 1][c + 1] === 0) {
cand.push([r, c + 1, 1]); cand.push([r, c, 0]);
}
}
for (const [nr, nc, nh] of cand) {
const k = key(nr, nc, nh);
if (!seen.has(k)) { seen.add(k); next.push([[nr, nc, nh], d + 1]); }
}
}
q = next;
}
return -1;
}class Solution {
public int minimumMoves(int[][] grid) {
int n = grid.length;
boolean[][][] seen = new boolean[n][n][2];
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{0, 0, 0, 0}); // r, c, h, dist
seen[0][0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], h = cur[2], d = cur[3];
if (r == n - 1 && c == n - 2 && h == 0) return d;
int[][] cand;
if (h == 0) {
cand = new int[][]{
(c + 2 < n && grid[r][c + 2] == 0) ? new int[]{r, c + 1, 0} : null,
(r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0) ? new int[]{r + 1, c, 0} : null,
(r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0) ? new int[]{r, c, 1} : null
};
} else {
cand = new int[][]{
(r + 2 < n && grid[r + 2][c] == 0) ? new int[]{r + 1, c, 1} : null,
(c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0) ? new int[]{r, c + 1, 1} : null,
(c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0) ? new int[]{r, c, 0} : null
};
}
for (int[] s : cand) {
if (s != null && !seen[s[0]][s[1]][s[2]]) {
seen[s[0]][s[1]][s[2]] = true;
q.add(new int[]{s[0], s[1], s[2], d + 1});
}
}
}
return -1;
}
}int minimumMoves(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<array<bool,2>>> seen(n, vector<array<bool,2>>(n, {false,false}));
queue<array<int,4>> q; // r, c, h, dist
q.push({0, 0, 0, 0});
seen[0][0][0] = true;
while (!q.empty()) {
auto [r, c, h, d] = q.front(); q.pop();
if (r == n - 1 && c == n - 2 && h == 0) return d;
vector<array<int,3>> cand;
if (h == 0) {
if (c + 2 < n && grid[r][c + 2] == 0) cand.push_back({r, c + 1, 0});
if (r + 1 < n && grid[r + 1][c] == 0 && grid[r + 1][c + 1] == 0) {
cand.push_back({r + 1, c, 0}); cand.push_back({r, c, 1});
}
} else {
if (r + 2 < n && grid[r + 2][c] == 0) cand.push_back({r + 1, c, 1});
if (c + 1 < n && grid[r][c + 1] == 0 && grid[r + 1][c + 1] == 0) {
cand.push_back({r, c + 1, 1}); cand.push_back({r, c, 0});
}
}
for (auto& s : cand) {
if (!seen[s[0]][s[1]][s[2]]) {
seen[s[0]][s[1]][s[2]] = true;
q.push({s[0], s[1], s[2], d + 1});
}
}
}
return -1;
}Explanation
The snake is a moving shape, not a single point, so we describe its position with a small state: the head cell (r, c) plus an orientation flag h (0 = horizontal, 1 = vertical). Once you think of each state as a node, "fewest moves" becomes a shortest-path problem, and BFS over states finds it.
BFS starts from the snake's opening state (0, 0, 0) at distance 0 and explores all states reachable in one move, then two moves, and so on. The first time it pops the target state (n-1, n-2, 0), the recorded distance is the minimum answer.
The heart of the code is generating the legal next states. If the snake is horizontal it can slide right (needs grid[r][c+2] empty), or — if the two cells below are empty — slide down or rotate clockwise into a vertical shape. The vertical case is the mirror image: slide down, slide right, or rotate counter-clockwise. A seen set stops us from re-expanding a state.
Example: on an open 4×4 grid the snake threads right and down, rotating only where the grid forces it, and BFS reports the smallest move count that lands it on the bottom-right two cells. If the target state is never reached, the loop ends and we return -1.
Because every move counts as one step and BFS visits states in distance order, the first arrival at the goal is provably optimal.