Minimum Moves to Reach Target with Rotations solution and explanation
4 more videos on this problem
Leetcode 1210 Minimum Moves to Reach Target with RotationsCoder on A Farm · 25:45 · 167 views
LeetCode Hard: 1210. Minimum Moves to Reach Target with Rotationsrobzingcod · 34:00 · 130 views
No Sound Leetcode 1210: Minimum Moves to Reach Target with RotationsExtremeProgrammer · 6:34 · 7 views
LeetCode 1210: Minimum Moves to Reach Target with RotationsAlitaCode · 31:19 · 3 views
LeetCode 1210: Minimum Moves to Reach Target with RotationsAlitaCode · 29:39
The problem
In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).
In one move the snake can:
- Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from
(r, c)and(r, c+1)to(r, c)and(r+1, c).
- Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case 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.
If there is no way to reach the target, return -1.
Example 1:
Input: 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]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].
Example 2:
Input: grid = [[0,0,1,1,1,1], [0,0,0,0,1,1], [1,1,0,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,0]] Output: 9
Constraints:
2 <= n <= 1000 <= grid[i][j] <= 1- It is guaranteed that the snake starts at empty cells.
Approach overview
Problem Overview: You control a 2‑cell snake inside an n x n grid. The snake can move right, move down, or rotate between horizontal and vertical positions if the surrounding cells are empty. The goal is to reach the bottom‑right target configuration using the minimum number of moves.
Approach 1: State Graph BFS (O(n2) time, O(n2) space)
The grid can be treated as a graph where each node represents the snake's state: the head position and its orientation (horizontal or vertical). From each state, generate valid transitions: move right, move down, or rotate if the required cells are free. Use Breadth-First Search to explore states level by level, since BFS guarantees the first time you reach the target configuration is the minimum number of moves. Maintain a visited set keyed by (row, col, orientation) to avoid revisiting the same configuration. The total number of states is at most 2 * n * n, giving O(n2) time and O(n2) space.
Approach 2: BFS with State Encoding and Transition Pruning (O(n2) time, O(n2) space)
This version keeps the same BFS idea but encodes the snake using the top‑left cell of the segment plus orientation. That representation avoids storing both cells explicitly and simplifies transition checks. When horizontal, you attempt: right shift, down shift, and clockwise rotation. When vertical, you attempt: down shift, right shift, and counter‑clockwise rotation. Each transition checks the required cells in the matrix to ensure they are within bounds and empty. Using a compact visited structure such as a boolean 3D array improves cache locality and keeps the BFS fast even when the grid is large.
The algorithm relies heavily on graph traversal concepts from Breadth-First Search and grid state modeling using arrays. Once the state representation is correct, transitions become straightforward conditional checks.
Recommended for interviews: The BFS state‑graph solution is the expected approach. Interviewers want to see how you model the snake configuration as a graph node and generate valid transitions. A naive exploration without visited tracking quickly explodes in states, while the BFS with state encoding shows strong problem‑modeling and graph traversal skills.
Approach 1: Breadth-First Search
Breadth-First Search (BFS) is a powerful technique for such grid-based traversal problems. The idea is to explore all potential moves that the snake can make from its current position and orientation, tracking the number of moves. Each state of the snake (defined by its head position and orientation) is enqueued with its move count. This ensures that the shortest path to the goal is found first, making BFS ideal for finding the minimum number of moves.
from collections import deque
def minimumMoves(grid):
n = len(grid)
target = ((n - 1, n - 2), (n - 1, n - 1))
visited = set()
queue = deque([((0, 0), (0, 1), 0)])
visited.add(((0, 0), (0, 1)))
while queue:
head, tail, moves = queue.popleft()
hx, hy = head
tx, ty = tail
if (head, tail) == target:
return moves
# Right move
if hy + 1 < n and grid[hx][hy + 1] == 0 and ty + 1 < n and grid[tx][ty + 1] == 0:
new_head = (hx, hy + 1)
new_tail = (tx, ty + 1)
if (new_head, new_tail) not in visited:
visited.add((new_head, new_tail))
queue.append((new_head, new_tail, moves + 1))
# Down move
if hx + 1 < n and grid[hx + 1][hy] == 0 and tx + 1 < n and grid[tx + 1][ty] == 0:
new_head = (hx + 1, hy)
new_tail = (tx + 1, ty)
if (new_head, new_tail) not in visited:
visited.add((new_head, new_tail))
queue.append((new_head, new_tail, moves + 1))
# Rotate clockwise (horizontal to vertical)
if hx == tx and tx + 1 < n and grid[tx + 1][ty] == 0 and grid[tx + 1][ty - 1] == 0:
new_head = (tx, ty - 1)
new_tail = (tx + 1, ty - 1)
if (new_head, new_tail) not in visited:
visited.add((new_head, new_tail))
queue.append((new_head, new_tail, moves + 1))
# Rotate counterclockwise (vertical to horizontal)
if hy == ty and hy + 1 < n and grid[hx][hy + 1] == 0 and grid[hx - 1][hy + 1] == 0:
new_head = (hx, hy)
new_tail = (hx, hy + 1)
if (new_head, new_tail) not in visited:
visited.add((new_head, new_tail))
queue.append((new_head, new_tail, moves + 1))
return -1import java.util.*;
public class Solution {
public int minimumMoves(int[][] grid) {
int n = grid.length;
int[][][] visited = new int[n][n][2];
for (int[][] mat : visited) {
for (int[] row : mat) {
Arrays.fill(row, -1);
}
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 0, 0});
visited[0][0][0] = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int head = cur[0], tail = cur[1], orient = cur[2], moves = cur[3];
if (head == n - 1 && tail == n - 2 && orient == 0) {
return moves;
}
int[] headXY = {head / n, head % n};
int[] tailXY = {tail / n, tail % n};
// Move to the right
if (orient == 0 && tailXY[1] + 1 < n && grid[tailXY[0]][tailXY[1] + 1] == 0) {
int hNew = tail;
int tNew = tail + 1;
if (visited[headXY[0]][(headXY[1]) + 1][orient] == -1) {
visited[headXY[0]][(headXY[1]) + 1][orient] = moves + 1;
queue.offer(new int[]{hNew, tNew, orient, moves + 1});
}
}
// Move down
if (orient == 0 && headXY[0] + 1 < n && grid[headXY[0] + 1][headXY[1]] == 0 && grid[tailXY[0] + 1][tailXY[1]] == 0) {
int hNew = head + n;
int tNew = tail + n;
if (visited[(headXY[0]) + 1][headXY[1]][orient] == -1) {
visited[(headXY[0]) + 1][headXY[1]][orient] = moves + 1;
queue.offer(new int[]{hNew, tNew, orient, moves + 1});
}
}
// Rotate clockwise
if (orient == 0 && headXY[0] + 1 < n && grid[tailXY[0] + 1][tailXY[1] - 1] == 0 && grid[tailXY[0] + 1][tailXY[1]] == 0) {
int hNew = head;
int tNew = head + n;
if (visited[(headXY[0])][headXY[1]][1] == -1) {
visited[(headXY[0])][headXY[1]][1] = moves + 1;
queue.offer(new int[]{hNew, tNew, 1, moves + 1});
}
}
// Rotate counterclockwise
if (orient == 1 && tailXY[1] + 1 < n && grid[headXY[0]][headXY[1] + 1] == 0 && grid[tailXY[0]][tailXY[1] + 1] == 0) {
int hNew = head;
int tNew = head + 1;
if (visited[headXY[0]][headXY[1]][0] == -1) {
visited[headXY[0]][headXY[1]][0] = moves + 1;
queue.offer(new int[]{hNew, tNew, 0, moves + 1});
}
}
}
return -1;
}
}#include <vector>
#include <queue>
#include <set>
using namespace std;
struct State {
pair<int, int> head;
pair<int, int> tail;
int moves;
};
int minimumMoves(vector<vector<int>>& grid) {
int n = grid.size();
pair<int, int> targetHead = {n - 1, n - 2};
pair<int, int> targetTail = {n - 1, n - 1};
set<pair<pair<int, int>, pair<int, int>>> visited;
queue<State> queue;
queue.push({{0, 0}, {0, 1}, 0});
visited.insert({{0, 0}, {0, 1}});
while (!queue.empty()) {
auto [head, tail, moves] = queue.front();
queue.pop();
if (head == targetHead && tail == targetTail) {
return moves;
}
auto [hx, hy] = head;
auto [tx, ty] = tail;
// Right move
if (hy + 1 < n && grid[hx][hy + 1] == 0 && ty + 1 < n && grid[tx][ty + 1] == 0) {
State newState = {{hx, hy + 1}, {tx, ty + 1}, moves + 1};
if (visited.insert({newState.head, newState.tail}).second) {
queue.push(newState);
}
}
// Down move
if (hx + 1 < n && grid[hx + 1][hy] == 0 && tx + 1 < n && grid[tx + 1][ty] == 0) {
State newState = {{hx + 1, hy}, {tx + 1, ty}, moves + 1};
if (visited.insert({newState.head, newState.tail}).second) {
queue.push(newState);
}
}
// Rotate clockwise
if (hx == tx && tx + 1 < n && grid[tx + 1][ty] == 0 && grid[tx + 1][ty - 1] == 0) {
State newState = {{tx, ty - 1}, {tx + 1, ty - 1}, moves + 1};
if (visited.insert({newState.head, newState.tail}).second) {
queue.push(newState);
}
}
// Rotate counterclockwise
if (hy == ty && hy + 1 < n && hx - 1 >= 0 && grid[hx][hy + 1] == 0 && grid[hx - 1][hy + 1] == 0) {
State newState = {{hx, hy}, {hx, hy + 1}, moves + 1};
if (visited.insert({newState.head, newState.tail}).second) {
queue.push(newState);
}
}
}
return -1;
}var minimumMoves = function(grid) {
const n = grid.length;
const queue = [[0, 0, 0, 0]]; // [head_x, head_y, orientation, moves]
const visited = new Set();
visited.add('0,0,0');
while (queue.length) {
const [hx, hy, orient, steps] = queue.shift();
if (hx === n - 1 && hy === n - 2 && orient === 0) return steps;
if (orient === 0 && hy + 1 < n && grid[hx][hy + 1] === 0) {
// Move right
if (!visited.has(`${hx},${hy + 1},0`)) {
visited.add(`${hx},${hy + 1},0`);
queue.push([hx, hy + 1, 0, steps + 1]);
}
// Rotate clockwise to vertical
if (hx + 1 < n && grid[hx + 1][hy] === 0) {
if (!visited.has(`${hx},${hy},1`)) {
visited.add(`${hx},${hy},1`);
queue.push([hx, hy, 1, steps + 1]);
}
}
}
if (orient === 1 && hx + 1 < n && grid[hx + 1][hy] === 0) {
// Move down
if (!visited.has(`${hx + 1},${hy},1`)) {
visited.add(`${hx + 1},${hy},1`);
queue.push([hx + 1, hy, 1, steps + 1]);
}
// Rotate counterclockwise to horizontal
if (hy + 1 < n && grid[hx][hy + 1] === 0) {
if (!visited.has(`${hx},${hy},0`)) {
visited.add(`${hx},${hy},0`);
queue.push([hx, hy, 0, steps + 1]);
}
}
}
}
return -1;
};This solution uses BFS. The queue holds tuples representing the head and tail of the snake along with the current number of moves. For each state, potential moves are checked (right, down, and rotations), and new states are added to the queue if they haven't been visited yet.
Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions.
Space Complexity: O(n^3), because of the growth in the queue and visited data structures.
Approach 2: BFS
The problem asks for the minimum number of moves for the snake to reach the target position from the starting position. We consider using Breadth-First Search (BFS) to solve it.
We define the following data structures or variables:
- Queue
q: Stores the current position of the snake. Each position is a tuple(a, b), wherearepresents the tail position of the snake, andbrepresents the head position of the snake. Initially, we add the position(0, 1)to the queueq. If we flatten the 2D maze into a 1D array, then the position(0, 1)represents the two cells with indices0and1in the 1D array. - Target position
target: The value is fixed at(n^2 - 2, n^2 - 1), which is the last two cells of the last row of the 2D maze. - Array or set
vis: Stores whether the current position state of the snake has been visited. Each state is a tuple(a, status), wherearepresents the tail position of the snake, andstatusrepresents the current state of the snake, with values of0or1, representing the horizontal and vertical states of the snake, respectively. Initially, add the state of the starting position(0, 1)to the setvis. - Answer variable
ans: Stores the number of moves for the snake to reach the target position from the starting position. Initially, it is0.
We use BFS to solve it. Each time we take a position from the queue q, we check whether the position is the target position target. If it is, we directly return the answer variable ans. If not, we add the next possible position of this position to the queue q and add this position to vis. Note that the next position could be the horizontal or vertical state of the snake, and we need to judge them separately (see the following code comments). At the end of each round of search, the answer variable ans increments by 1.
Finally, if the queue q is empty, it means that it is impossible to reach the target position from the starting position, so return -1.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of rows or columns of the 2D maze.
function minimumMoves(grid: number[][]): number {
const n = grid.length;
const target: number[] = [n * n - 2, n * n - 1];
const q: number[][] = [[0, 1]];
const vis = Array.from({ length: n * n }, () => Array(2).fill(false));
vis[0][0] = true;
const move = (i1: number, j1: number, i2: number, j2: number) => {
if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n && j2 >= 0 && j2 < n) {
const a = i1 * n + j1;
const b = i2 * n + j2;
const status = i1 === i2 ? 0 : 1;
if (!vis[a][status] && grid[i1][j1] == 0 && grid[i2][j2] == 0) {
q.push([a, b]);
vis[a][status] = true;
}
}
};
let ans = 0;
while (q.length) {
for (let k = q.length; k; --k) {
const p: number[] = q.shift();
if (p[0] === target[0] && p[1] === target[1]) {
return ans;
}
const [i1, j1] = [~~(p[0] / n), p[0] % n];
const [i2, j2] = [~~(p[1] / n), p[1] % n];
// 尝试向右平移（保持身体水平/垂直状态）
move(i1, j1 + 1, i2, j2 + 1);
// 尝试向下平移（保持身体水平/垂直状态）
move(i1 + 1, j1, i2 + 1, j2);
// 当前处于水平状态，且 grid[i1 + 1][j2] 无障碍，尝试顺时针旋转90°
if (i1 == i2 && i1 + 1 < n && grid[i1 + 1][j2] == 0) {
move(i1, j1, i1 + 1, j1);
}
// 当前处于垂直状态，且 grid[i2][j1 + 1] 无障碍，尝试逆时针旋转90°
if (j1 == j2 && j1 + 1 < n && grid[i2][j1 + 1] == 0) {
move(i1, j1, i1, j1 + 1);
}
}
++ans;
}
return -1;
}func minimumMoves(grid [][]int) int {
n := len(grid)
type pair struct{ a, b int }
target := pair{n*n - 2, n*n - 1}
q := []pair{pair{0, 1}}
vis := make([][2]bool, n*n)
vis[0][0] = true
move := func(i1, j1, i2, j2 int) {
if i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n && j2 >= 0 && j2 < n {
a, b := i1*n+j1, i2*n+j2
status := 1
if i1 == i2 {
status = 0
}
if !vis[a][status] && grid[i1][j1] == 0 && grid[i2][j2] == 0 {
q = append(q, pair{a, b})
vis[a][status] = true
}
}
}
ans := 0
for len(q) > 0 {
for k := len(q); k > 0; k-- {
p := q[0]
q = q[1:]
if p == target {
return ans
}
a, b := p.a, p.b
i1, j1 := a/n, a%n
i2, j2 := b/n, b%n
// 尝试向右平移（保持身体水平/垂直状态）
move(i1, j1+1, i2, j2+1)
// 尝试向下平移（保持身体水平/垂直状态）
move(i1+1, j1, i2+1, j2)
// 当前处于水平状态，且 grid[i1 + 1][j2] 无障碍，尝试顺时针旋转90°
if i1 == i2 && i1+1 < n && grid[i1+1][j2] == 0 {
move(i1, j1, i1+1, j1)
}
// 当前处于垂直状态，且 grid[i2][j1 + 1] 无障碍，尝试逆时针旋转90°
if j1 == j2 && j1+1 < n && grid[i2][j1+1] == 0 {
move(i1, j1, i1, j1+1)
}
}
ans++
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search | Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive BFS without state pruning | Exponential | High | Conceptual understanding of transitions; not practical for large grids |
| BFS with (row, col, orientation) state | O(n^2) | O(n^2) | General optimal solution for finding minimum moves in the grid |
| BFS with compact state encoding | O(n^2) | O(n^2) | Production or interview code where efficient state checks and clean transitions matter |
Frequently asked questions
Is Minimum Moves to Reach Target with Rotations easy or hard?
Minimum Moves to Reach Target with Rotations is classified as a Hard problem on LeetCode. The challenge comes from correctly modeling the snake state, handling rotation constraints, and generating valid BFS transitions without missing edge cases.
Minimum Moves to Reach Target with Rotations Python/Java solution
Implement BFS using a queue where each entry contains the snake position and orientation. For Python, use collections.deque and a set or boolean visited array. Java implementations typically use a Queue with a boolean[][][] visited structure for fast lookups.
How to solve Minimum Moves to Reach Target with Rotations in O(n^2)?
Model each snake configuration as a graph node defined by (row, column, orientation). Use Breadth-First Search to explore valid transitions such as moving right, moving down, or rotating when adjacent cells are empty. Track visited states to prevent revisiting configurations.
What is the best approach for Minimum Moves to Reach Target with Rotations?
The best approach is Breadth-First Search (BFS) over snake states. Each state stores the snake's position and orientation (horizontal or vertical). BFS explores all valid moves level by level, guaranteeing the first time the target configuration is reached is the minimum number of moves.
Is Minimum Moves to Reach Target with Rotations asked at Google/Amazon/Meta?
Grid BFS and state‑transition problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The problem tests graph modeling, BFS traversal, and careful handling of state transitions in matrix problems.
What data structure is used in Minimum Moves to Reach Target with Rotations?
The core data structure is a queue used in Breadth-First Search. A visited set or 3D boolean array tracks explored states defined by grid position and snake orientation, preventing repeated exploration of the same configuration.
What is the time complexity of Minimum Moves to Reach Target with Rotations?
The optimal BFS solution runs in O(n^2) time and O(n^2) space for an n x n grid. There are at most 2 * n * n possible snake states because each cell can be the head of either a horizontal or vertical configuration.