# 1210. Minimum Moves to Reach Target with Rotations

• Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 enum class Pos { HORIZONTAL, VERTICAL }; class Solution { public: int minimumMoves(vector>& grid) { const int n = grid.size(); int ans = 0; // state of (x, y, pos) // pos := 0 (horizontal) / 1 (vertical) queue> q{{{0, 0, Pos::HORIZONTAL}}}; vector>> seen(n, vector>(n, vector(2))); seen[0][0][static_cast(Pos::HORIZONTAL)] = true; auto canMoveRight = [&](int x, int y, Pos pos) -> bool { if (pos == Pos::HORIZONTAL) 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::VERTICAL) 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::HORIZONTAL && x + 1 < n && !grid[x + 1][y + 1] && !grid[x + 1][y]; }; auto canRotateCounterclockwise = [&](int x, int y, Pos pos) -> bool { return pos == Pos::VERTICAL && y + 1 < n && !grid[x + 1][y + 1] && !grid[x][y + 1]; }; while (!q.empty()) { 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::HORIZONTAL) return ans; if (canMoveRight(x, y, pos) && !seen[x][y + 1][static_cast(pos)]) { q.emplace(x, y + 1, pos); seen[x][y + 1][static_cast(pos)] = true; } if (canMoveDown(x, y, pos) && !seen[x + 1][y][static_cast(pos)]) { q.emplace(x + 1, y, pos); seen[x + 1][y][static_cast(pos)] = true; } const Pos newPos = pos == Pos::HORIZONTAL ? Pos::VERTICAL : Pos::HORIZONTAL; if ((canRotateClockwise(x, y, pos) || canRotateCounterclockwise(x, y, pos)) && !seen[x][y][static_cast(newPos)]) { q.emplace(x, y, newPos); seen[x][y][static_cast(newPos)] = true; } } ++ans; } return -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 enum Pos { HORIZONTAL, VERTICAL } class Solution { public int minimumMoves(int[][] grid) { final int n = grid.length; int ans = 0; // state of (x, y, pos) // pos := 0 (horizontal) / 1 (vertical) Queue q = new ArrayDeque<>(Arrays.asList(new int[] {0, 0, Pos.HORIZONTAL.ordinal()})); boolean[][][] seen = new boolean[n][n][2]; seen[0][0][Pos.HORIZONTAL.ordinal()] = true; while (!q.isEmpty()) { for (int sz = q.size(); sz > 0; --sz) { final int x = q.peek()[0]; final int y = q.peek()[1]; final int pos = q.poll()[2]; if (x == n - 1 && y == n - 2 && pos == Pos.HORIZONTAL.ordinal()) return ans; if (canMoveRight(grid, x, y, pos) && !seen[x][y + 1][pos]) { q.offer(new int[] {x, y + 1, pos}); seen[x][y + 1][pos] = true; } if (canMoveDown(grid, x, y, pos) && !seen[x + 1][y][pos]) { q.offer(new int[] {x + 1, y, pos}); seen[x + 1][y][pos] = true; } final int newPos = pos == Pos.HORIZONTAL.ordinal() ? Pos.VERTICAL.ordinal() : Pos.HORIZONTAL.ordinal(); if ((canRotateClockwise(grid, x, y, pos) || canRotateCounterclockwise(grid, x, y, pos)) && !seen[x][y][newPos]) { q.offer(new int[] {x, y, newPos}); seen[x][y][newPos] = true; } } ++ans; } return -1; } private boolean canMoveRight(int[][] grid, int x, int y, int pos) { if (pos == Pos.HORIZONTAL.ordinal()) 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, int pos) { if (pos == Pos.VERTICAL.ordinal()) 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, int pos) { return pos == Pos.HORIZONTAL.ordinal() && x + 1 < grid.length && grid[x + 1][y + 1] == 0 && grid[x + 1][y] == 0; }; private boolean canRotateCounterclockwise(int[][] grid, int x, int y, int pos) { return pos == Pos.VERTICAL.ordinal() && y + 1 < grid.length && grid[x + 1][y + 1] == 0 && grid[x][y + 1] == 0; }; } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 from enum import IntEnum class Pos(IntEnum): HORIZONTAL = 0 VERTICAL = 1 class Solution: def minimumMoves(self, grid: List[List[int]]) -> int: n = len(grid) ans = 0 # state of (x, y, pos) # pos := 0 (horizontal) // 1 (vertical) q = deque([(0, 0, Pos.HORIZONTAL)]) seen = {(0, 0, Pos.HORIZONTAL)} def canMoveRight(x: int, y: int, pos: Pos) -> bool: if pos == Pos.HORIZONTAL: 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.VERTICAL: 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.HORIZONTAL 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.VERTICAL 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.HORIZONTAL: 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.VERTICAL if pos == Pos.HORIZONTAL else Pos.HORIZONTAL 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