# 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 { kHorizontal, kVertical }; class Solution { public: int minimumMoves(vector>& grid) { const int n = grid.size(); int ans = 0; // the state of (x, y, pos) // pos := 0 (horizontal) / 1 (vertical) queue> q{{{0, 0, Pos::kHorizontal}}}; vector>> seen(n, vector>(n, vector(2))); seen[0][0][static_cast(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]; }; 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::kHorizontal) 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::kHorizontal ? Pos::kVertical : Pos::kHorizontal; 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 { kHorizontal, kVertical } class Solution { public int minimumMoves(int[][] grid) { final int n = grid.length; int ans = 0; // the state of (x, y, pos) // pos := 0 (horizontal) / 1 (vertical) Queue q = new ArrayDeque<>(Arrays.asList(new int[] {0, 0, Pos.kHorizontal.ordinal()})); boolean[][][] seen = new boolean[n][n][2]; seen[0][0][Pos.kHorizontal.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.kHorizontal.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.kHorizontal.ordinal() ? Pos.kVertical.ordinal() : Pos.kHorizontal.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.kHorizontal.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.kVertical.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.kHorizontal.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.kVertical.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): 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