##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1210.html

# 1210. Minimum Moves to Reach Target with Rotations (Hard)

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 <= 100
• 0 <= grid[i][j] <= 1
• It is guaranteed that the snake starts at empty cells.

Related Topics:

## Solution 1. BFS

Since we are looking for the shortest path, BFS is our first option.

// OJ: https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int minimumMoves(vector<vector<int>>& G) {
queue<int> q;
q.push(0);
unordered_set<int> seen;
seen.insert(0);
int step = 0, N = G.size();
auto safe = [&](int p) {
int y = p % 1000, x = p / 1000 % 1000, dir = p / 1000000;
if (x < 0 || y < 0 || x >= N || y >= N || G[x][y] == 1) return false;
return (dir == 0 && y + 1 < N && G[x][y + 1] == 0)
|| (dir == 1 && x + 1 < N && G[x + 1][y] == 0);
};
while (q.size()) {
int cnt = q.size();
while (cnt--) {
int p = q.front(), y = p % 1000, x = p / 1000 % 1000, dir = p / 1000000;
if (x == N - 1 && y == N - 2) return step;
q.pop();
// move right
int r = p + 1;
if (seen.count(r) == 0 && safe(r)) {
seen.insert(r);
q.push(r);
}
// move down
int d = p + 1000;
if (seen.count(d) == 0 && safe(d)) {
seen.insert(d);
q.push(d);
}
// rotate closewise
if (dir == 0) {
int p2 = 1000000 + x * 1000 + y, cx = x + 1, cy = y + 1;
if (seen.count(p2) || !safe(p2) || cx < 0 || cy < 0 || cx >= N || cy >= N || G[cx][cy] == 1) continue;
seen.insert(p2);
q.push(p2);
}
// rotate counterclosewise
if (dir == 1) {
int p2 = x * 1000 + y, cx = x + 1, cy = y + 1;
if (seen.count(p2) || !safe(p2) || cx < 0 || cy < 0 || cx >= N || cy >= N || G[cx][cy] == 1) continue;
seen.insert(p2);
q.push(p2);
}
}
++step;
}
return -1;
}
};

• class Solution {
public int minimumMoves(int[][] grid) {
final int BLOCK = -1;
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
int rows = grid.length, columns = grid[0].length;
if (grid[rows - 1][columns - 1] == 1 || grid[rows - 1][columns - 2] == -1)
return -1;
int[][][] colors = new int[rows][columns][2];
int[][][] distances = new int[rows][columns][2];
for (int i = 0; i < rows; i++)
colors[i][columns - 1][0] = BLOCK;
for (int i = 0; i < columns; i++)
colors[rows - 1][i][1] = BLOCK;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (grid[i][j] == 1) {
colors[i][j][0] = BLOCK;
colors[i][j][1] = BLOCK;
if (i > 0)
colors[i - 1][j][1] = BLOCK;
if (j > 0)
colors[i][j - 1][0] = BLOCK;
}
distances[i][j][0] = Integer.MAX_VALUE;
distances[i][j][1] = Integer.MAX_VALUE;
}
}
colors[0][0][0] = GRAY;
distances[0][0][0] = 0;
queue.offer(new int[]{0, 0, 0});
while (!queue.isEmpty()) {
int[] status = queue.poll();
int row = status[0], column = status[1], direction = status[2];
int distance = distances[row][column][direction];
int newRow = row + 1, newColumn = column + 1, newDirection = 1 - direction;
int newDistance = distance + 1;
if (newRow < rows && colors[newRow][column][direction] == WHITE) {
colors[newRow][column][direction] = GRAY;
distances[newRow][column][direction] = newDistance;
queue.offer(new int[]{newRow, column, direction});
}
if (newColumn < columns && colors[row][newColumn][direction] == WHITE) {
colors[row][newColumn][direction] = GRAY;
distances[row][newColumn][direction] = newDistance;
queue.offer(new int[]{row, newColumn, direction});
}
if (colors[row][column][newDirection] == WHITE) {
if (row < rows - 1 && column < columns - 1 && grid[row + 1][column + 1] == 0) {
colors[row][column][newDirection] = GRAY;
distances[row][column][newDirection] = newDistance;
queue.offer(new int[]{row, column, newDirection});
}
}
colors[row][column][direction] = BLACK;
}
int totalMoves = distances[rows - 1][columns - 2][0];
}
}

############

class Solution {
private int n;
private int[][] grid;
private boolean[][] vis;
private Deque<int[]> q = new ArrayDeque<>();

public int minimumMoves(int[][] grid) {
this.grid = grid;
n = grid.length;
vis = new boolean[n * n][2];
int[] target = {n * n - 2, n * n - 1};
q.offer(new int[] {0, 1});
vis[0][0] = true;
int ans = 0;
while (!q.isEmpty()) {
for (int k = q.size(); k > 0; --k) {
var p = q.poll();
if (p[0] == target[0] && p[1] == target[1]) {
return ans;
}
int i1 = p[0] / n, j1 = p[0] % n;
int i2 = p[1] / n, j2 = p[1] % n;
move(i1, j1 + 1, i2, j2 + 1);
move(i1 + 1, j1, i2 + 1, j2);
if (i1 == i2 && i1 + 1 < n && grid[i1 + 1][j2] == 0) {
move(i1, j1, i1 + 1, j1);
}
if (j1 == j2 && j1 + 1 < n && grid[i2][j1 + 1] == 0) {
move(i1, j1, i1, j1 + 1);
}
}
++ans;
}
return -1;
}

private void move(int i1, int j1, int i2, int j2) {
if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n && i2 >= 0 && i2 < n && j2 >= 0 && j2 < n) {
int a = i1 * n + j1, b = i2 * n + j2;
int status = i1 == i2 ? 0 : 1;
if (!vis[a][status] && grid[i1][j1] == 0 && grid[i2][j2] == 0) {
q.offer(new int[] {a, b});
vis[a][status] = true;
}
}
}
}

• // OJ: https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int minimumMoves(vector<vector<int>>& G) {
queue<int> q;
q.push(0);
unordered_set<int> seen;
seen.insert(0);
int step = 0, N = G.size();
auto safe = [&](int p) {
int y = p % 1000, x = p / 1000 % 1000, dir = p / 1000000;
if (x < 0 || y < 0 || x >= N || y >= N || G[x][y] == 1) return false;
return (dir == 0 && y + 1 < N && G[x][y + 1] == 0)
|| (dir == 1 && x + 1 < N && G[x + 1][y] == 0);
};
while (q.size()) {
int cnt = q.size();
while (cnt--) {
int p = q.front(), y = p % 1000, x = p / 1000 % 1000, dir = p / 1000000;
if (x == N - 1 && y == N - 2) return step;
q.pop();
// move right
int r = p + 1;
if (seen.count(r) == 0 && safe(r)) {
seen.insert(r);
q.push(r);
}
// move down
int d = p + 1000;
if (seen.count(d) == 0 && safe(d)) {
seen.insert(d);
q.push(d);
}
// rotate closewise
if (dir == 0) {
int p2 = 1000000 + x * 1000 + y, cx = x + 1, cy = y + 1;
if (seen.count(p2) || !safe(p2) || cx < 0 || cy < 0 || cx >= N || cy >= N || G[cx][cy] == 1) continue;
seen.insert(p2);
q.push(p2);
}
// rotate counterclosewise
if (dir == 1) {
int p2 = x * 1000 + y, cx = x + 1, cy = y + 1;
if (seen.count(p2) || !safe(p2) || cx < 0 || cy < 0 || cx >= N || cy >= N || G[cx][cy] == 1) continue;
seen.insert(p2);
q.push(p2);
}
}
++step;
}
return -1;
}
};

• class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
def move(i1, j1, i2, j2):
if 0 <= i1 < n and 0 <= j1 < n and 0 <= i2 < n and 0 <= j2 < n:
a, b = i1 * n + j1, i2 * n + j2
status = 0 if i1 == i2 else 1
if (a, status) not in vis and grid[i1][j1] == 0 and grid[i2][j2] == 0:
q.append((a, b))

n = len(grid)
target = (n * n - 2, n * n - 1)
q = deque([(0, 1)])
vis = {(0, 0)}
ans = 0
while q:
for _ in range(len(q)):
a, b = q.popleft()
if (a, b) == target:
return ans
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)
if i1 == i2 and i1 + 1 < n and grid[i1 + 1][j2] == 0:
move(i1, j1, i1 + 1, j1)
if j1 == j2 and j1 + 1 < n and grid[i2][j1 + 1] == 0:
move(i1, j1, i1, j1 + 1)
ans += 1
return -1

############

# 1210. Minimum Moves to Reach Target with Rotations
# https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations

class Solution:
def minimumMoves(self, grid: List[List[int]]) -> int:
n = len(grid)
start = (0, 0, 0, 1)
end = (n - 1, n - 2, n - 1, n - 1)
curr_level = {start}
moves = 0
visited = set()

while curr_level:
next_level = set()
for pos in curr_level:
r1, c1, r2, c2 = pos

# down
if c1 + 1 < n and grid[r1][c1+1] == 0 and c2 + 1 < n and grid[r2][c2+1] == 0:
if (r1, c1 + 1, r2, c2 + 1) not in visited:
next_level.add((r1, c1 + 1, r2, c2 + 1))

# right
if r1 + 1 < n and grid[r1+1][c1] == 0 and r2 + 1 < n and grid[r2+1][c2] == 0:
if (r1 + 1, c1, r2 + 1, c1) not in visited:
next_level.add((r1 + 1, c1, r2 + 1, c2))

# clockwise
if r1 == r2 and c2 == c1 + 1 and r1 + 1 < n and grid[r1+1][c1] + grid[r1+1][c1+1] == 0 :
if (r1, c1, r1 + 1, c1) not in visited:
next_level.add((r1, c1, r1 + 1, c1))

# counter-clockwise
if c1 == c2 and r2 == r1 + 1 and c1 + 1 < n and grid[r1][c1+1] + grid[r1+1][c1+1] == 0:
if (r1, c1, r1, c1 + 1) not in visited:
next_level.add((r1, c1, r1, c1 + 1))

if end in next_level: return moves + 1

curr_level = next_level
moves += 1

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)
if i1 == i2 && i1+1 < n && grid[i1+1][j2] == 0 {
move(i1, j1, i1+1, j1)
}
if j1 == j2 && j1+1 < n && grid[i2][j1+1] == 0 {
move(i1, j1, i1, j1+1)
}
}
ans++
}
return -1
}

• 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);
if (i1 == i2 && i1 + 1 < n && grid[i1 + 1][j2] == 0) {
move(i1, j1, i1 + 1, j1);
}
if (j1 == j2 && j1 + 1 < n && grid[i2][j1 + 1] == 0) {
move(i1, j1, i1, j1 + 1);
}
}
++ans;
}
return -1;
}


• /**
* @param {number[][]} grid
* @return {number}
*/
var minimumMoves = function (grid) {
const n = grid.length;
const target = [n * n - 2, n * n - 1];
const q = [[0, 1]];
const vis = Array.from({ length: n * n }, () => Array(2).fill(false));
vis[0][0] = true;

const move = (i1, j1, i2, j2) => {
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 = 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);
if (i1 == i2 && i1 + 1 < n && grid[i1 + 1][j2] == 0) {
move(i1, j1, i1 + 1, j1);
}
if (j1 == j2 && j1 + 1 < n && grid[i2][j1 + 1] == 0) {
move(i1, j1, i1, j1 + 1);
}
}
++ans;
}
return -1;
};