Time: O(n2)O(n2) Space: O(n2)O(n2)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom enum import IntEnum\n\n\nclass Pos(IntEnum):\n  kHorizontal = 0\n  kVertical = 1\n\n\nclass Solution:\n  def minimumMoves(self, grid: List[List[int]]) -> int:\n    n = len(grid)\n    ans = 0\n    # State of (x, y, pos)\n    # Pos := 0 (horizontal) // 1 (vertical)\n    q = collections.deque([(0, 0, Pos.kHorizontal)])\n    seen = {(0, 0, Pos.kHorizontal)}\n\n    def canMoveRight(x: int, y: int, pos: Pos) -> bool:\n      if pos == Pos.kHorizontal:\n        return y + 2 < n and not grid[x][y + 2]\n      return y + 1 < n and not grid[x][y + 1] and not grid[x + 1][y + 1]\n\n    def canMoveDown(x: int, y: int, pos: Pos) -> bool:\n      if pos == Pos.kVertical:\n        return x + 2 < n and not grid[x + 2][y]\n      return x + 1 < n and not grid[x + 1][y] and not grid[x + 1][y + 1]\n\n    def canRotateClockwise(x: int, y: int, pos: Pos) -> bool:\n      return pos == Pos.kHorizontal and x + 1 < n and \\\n          not grid[x + 1][y + 1] and not grid[x + 1][y]\n\n    def canRotateCounterclockwise(x: int, y: int, pos: Pos) -> bool:\n      return pos == Pos.kVertical and y + 1 < n and \\\n          not grid[x + 1][y + 1] and not grid[x][y + 1]\n\n    while q:\n      for _ in range(len(q)):\n        x, y, pos = q.popleft()\n        if x == n - 1 and y == n - 2 and pos == Pos.kHorizontal:\n          return ans\n        if canMoveRight(x, y, pos) and (x, y + 1, pos) not in seen:\n          q.append((x, y + 1, pos))\n          seen.add((x, y + 1, pos))\n        if canMoveDown(x, y, pos) and (x + 1, y, pos) not in seen:\n          q.append((x + 1, y, pos))\n          seen.add((x + 1, y, pos))\n        newPos = Pos.kVertical if pos == Pos.kHorizontal else Pos.kHorizontal\n        if (canRotateClockwise(x, y, pos) or canRotateCounterclockwise(x, y, pos)) and \\\n                (x, y, newPos) not in seen:\n          q.append((x, y, newPos))\n          seen.add((x, y, newPos))\n      ans += 1\n\n    return -1\n\n```
['Python3']