1210. Minimum Moves to Reach Target with Rotations LeetCode Solution
In this guide, you will get 1210. Minimum Moves to Reach Target with Rotations LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Reach Target with Rotations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Moves to Reach Target with Rotations
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.
2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
1210. Minimum Moves to Reach Target with Rotations LeetCode Solution in C++
enum class Pos { kHorizontal, kVertical };
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
const int n = grid.size();
queue<tuple<int, int, Pos>> q{{{0, 0, Pos::kHorizontal}}};
vector<vector<vector<bool>>> seen(n,
vector<vector<bool>>(n, vector<bool>(2)));
seen[0][0][static_cast<int>(Pos::kHorizontal)] = true;
auto canMoveRight = [&](int x, int y, Pos pos) -> bool {
if (pos == Pos::kHorizontal)
return y + 2 < n && !grid[x][y + 2];
return y + 1 < n && !grid[x][y + 1] && !grid[x + 1][y + 1];
};
auto canMoveDown = [&](int x, int y, Pos pos) -> bool {
if (pos == Pos::kVertical)
return x + 2 < n && !grid[x + 2][y];
return x + 1 < n && !grid[x + 1][y] && !grid[x + 1][y + 1];
};
auto canRotateClockwise = [&](int x, int y, Pos pos) -> bool {
return pos == Pos::kHorizontal && x + 1 < n && !grid[x + 1][y + 1] &&
!grid[x + 1][y];
};
auto canRotateCounterclockwise = [&](int x, int y, Pos pos) -> bool {
return pos == Pos::kVertical && y + 1 < n && !grid[x + 1][y + 1] &&
!grid[x][y + 1];
};
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [x, y, pos] = q.front();
q.pop();
if (x == n - 1 && y == n - 2 && pos == Pos::kHorizontal)
return step;
if (canMoveRight(x, y, pos) && !seen[x][y + 1][static_cast<int>(pos)]) {
q.emplace(x, y + 1, pos);
seen[x][y + 1][static_cast<int>(pos)] = true;
}
if (canMoveDown(x, y, pos) && !seen[x + 1][y][static_cast<int>(pos)]) {
q.emplace(x + 1, y, pos);
seen[x + 1][y][static_cast<int>(pos)] = true;
}
const Pos newPos =
pos == Pos::kHorizontal ? Pos::kVertical : Pos::kHorizontal;
if ((canRotateClockwise(x, y, pos) ||
canRotateCounterclockwise(x, y, pos)) &&
!seen[x][y][static_cast<int>(newPos)]) {
q.emplace(x, y, newPos);
seen[x][y][static_cast<int>(newPos)] = true;
}
}
return -1;
}
}; /* code provided by PROGIEZ */
1210. Minimum Moves to Reach Target with Rotations LeetCode Solution in Java
enum Pos { kHorizontal, kVertical }
class Solution {
public int minimumMoves(int[][] grid) {
record T(int x, int y, Pos pos) {}
final int n = grid.length;
Queue<T> q = new ArrayDeque<>(List.of(new T(0, 0, Pos.kHorizontal)));
boolean[][][] seen = new boolean[n][n][2];
seen[0][0][Pos.kHorizontal.ordinal()] = true;
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int x = q.peek().x;
final int y = q.peek().y;
final Pos pos = q.poll().pos;
if (x == n - 1 && y == n - 2 && pos == Pos.kHorizontal)
return step;
if (canMoveRight(grid, x, y, pos) && !seen[x][y + 1][pos.ordinal()]) {
q.offer(new T(x, y + 1, pos));
seen[x][y + 1][pos.ordinal()] = true;
}
if (canMoveDown(grid, x, y, pos) && !seen[x + 1][y][pos.ordinal()]) {
q.offer(new T(x + 1, y, pos));
seen[x + 1][y][pos.ordinal()] = true;
}
final Pos newPos = pos == Pos.kHorizontal ? Pos.kVertical : Pos.kHorizontal;
if ((canRotateClockwise(grid, x, y, pos) || canRotateCounterclockwise(grid, x, y, pos)) &&
!seen[x][y][newPos.ordinal()]) {
q.offer(new T(x, y, newPos));
seen[x][y][newPos.ordinal()] = true;
}
}
return -1;
}
private boolean canMoveRight(int[][] grid, int x, int y, Pos pos) {
if (pos == Pos.kHorizontal)
return y + 2 < grid.length && grid[x][y + 2] == 0;
return y + 1 < grid.length && grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0;
}
private boolean canMoveDown(int[][] grid, int x, int y, Pos pos) {
if (pos == Pos.kVertical)
return x + 2 < grid.length && grid[x + 2][y] == 0;
return x + 1 < grid.length && grid[x + 1][y] == 0 && grid[x + 1][y + 1] == 0;
}
private boolean canRotateClockwise(int[][] grid, int x, int y, Pos pos) {
return pos == Pos.kHorizontal && x + 1 < grid.length && grid[x + 1][y + 1] == 0 &&
grid[x + 1][y] == 0;
}
private boolean canRotateCounterclockwise(int[][] grid, int x, int y, Pos pos) {
return pos == Pos.kVertical && y + 1 < grid.length && grid[x + 1][y + 1] == 0 &&
grid[x][y + 1] == 0;
}
} // code provided by PROGIEZ
1210. Minimum Moves to Reach Target with Rotations LeetCode Solution in Python
from enum import IntEnum
class Pos(IntEnum):
kHorizontal = 0
kVertical = 1
class Solution:
def minimumMoves(self, grid: list[list[int]]) -> int:
n = len(grid)
ans = 0
# the state of (x, y, pos)
# pos := 0 (horizontal) / 1 (vertical)
q = collections.deque([(0, 0, Pos.kHorizontal)])
seen = {(0, 0, Pos.kHorizontal)}
def canMoveRight(x: int, y: int, pos: Pos) -> bool:
if pos == Pos.kHorizontal:
return y + 2 < n and not grid[x][y + 2]
return y + 1 < n and not grid[x][y + 1] and not grid[x + 1][y + 1]
def canMoveDown(x: int, y: int, pos: Pos) -> bool:
if pos == Pos.kVertical:
return x + 2 < n and not grid[x + 2][y]
return x + 1 < n and not grid[x + 1][y] and not grid[x + 1][y + 1]
def canRotateClockwise(x: int, y: int, pos: Pos) -> bool:
return (pos == Pos.kHorizontal and x + 1 < n and
not grid[x + 1][y + 1] and not grid[x + 1][y])
def canRotateCounterclockwise(x: int, y: int, pos: Pos) -> bool:
return (pos == Pos.kVertical and y + 1 < n and
not grid[x + 1][y + 1] and not grid[x][y + 1])
while q:
for _ in range(len(q)):
x, y, pos = q.popleft()
if x == n - 1 and y == n - 2 and pos == Pos.kHorizontal:
return ans
if canMoveRight(x, y, pos) and (x, y + 1, pos) not in seen:
q.append((x, y + 1, pos))
seen.add((x, y + 1, pos))
if canMoveDown(x, y, pos) and (x + 1, y, pos) not in seen:
q.append((x + 1, y, pos))
seen.add((x + 1, y, pos))
newPos = Pos.kVertical if pos == Pos.kHorizontal else Pos.kHorizontal
if ((canRotateClockwise(x, y, pos) or
canRotateCounterclockwise(x, y, pos)) and
(x, y, newPos) not in seen):
q.append((x, y, newPos))
seen.add((x, y, newPos))
ans += 1
return -1 # code by PROGIEZ
