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:
Breadth-first Search
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<int[]> queue = new LinkedList<int[]>(); 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]; return totalMoves == Integer.MAX_VALUE ? -1 : totalMoves; } } ############ 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)) vis.add((a, status)) 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: visited.add(pos) 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; };