MinMax in Python
Intuition\nAlice aims to maximize the total moves, while Bob tries to minimize them. This sounds like a Minimax problem to me.\n\n# Approach\nThe GetPawn functi
# Intuition\nAlice aims to maximize the total moves, while Bob tries to minimize them. This sounds like a [Minimax](https://en.wikipedia.org/wiki/Minimax) problem to me.\n\n# Approach\nThe `GetPawn` function calculates the minimum steps required for the knight to reach a given pawn using Breadth-First Search (BFS).\n\nThe `minMax` function recursively evaluates all possible moves for Alice and Bob, updating the total moves based on whose turn it is.\n\nThe recursion continues until all pawns are captured, and the maximum total moves that Alice can achieve are returned.\n\n\n# Complexity\n- **Time complexity**: \n  - Each `GetPawn` call is O(M\xB2), where M = 50 is the board size.\n  - Minimax explores all pawn capture permutations, leading to O(N!) recursive calls, where N is the number of pawns.\n  - Overall complexity: O(N! * M\xB2).\n\n- **Space complexity**: \n  - Each `GetPawn` call uses O(M\xB2) space for BFS.\n  - Caching in Minimax stores results for O(N!) states.\n  - Overall space complexity: O(N! * M\xB2).\n# Code\n```python\n\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]\n        positions = tuple([tuple(pawn) for pawn in positions])\n\n        @cache\n        def GetPawn(start: Tuple[int, int], pawn: Tuple[int, int]) -> int:\n            directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]\n            queue = deque([(start[0], start[1], 0)])\n            visited = set((start[0], start[1]))\n\n            while queue:\n                cx, cy, step = queue.popleft()\n                if (cx, cy) == pawn:\n                    return step\n\n                for dx, dy in directions:\n                    nx, ny = cx + dx, cy + dy\n                    if 0 <= nx < 50 and 0 <= ny < 50 and (nx, ny) not in visited:\n                        queue.append((nx, ny, step + 1))\n                        visited.add((nx, ny))\n\n            return float(\'inf\')  # Unreachable\n\n        @cache\n        def minMax(cposition, positions, turn):\n            if not positions:\n                return 0\n            \n            # Alice\'s turn: maximize total moves\n            if turn:\n                total_moves = -float(\'inf\')\n                for i in range(len(positions)):\n                    pawn = positions[i]\n                    steps = GetPawn(tuple(cposition), pawn) + minMax(pawn, positions[:i] + positions[i + 1:], not turn)\n                    total_moves = max(total_moves, steps)\n                return total_moves\n            \n            # Bob\'s turn: minimize total moves\n            else:\n                total_moves = float(\'inf\')\n                for i in range(len(positions)):\n                    pawn = positions[i]\n                    steps = GetPawn(cposition, pawn) + minMax(pawn, positions[:i] + positions[i + 1:], not turn)\n                    total_moves = min(total_moves, steps)\n                return total_moves\n        \n        return minMax((kx, ky), positions, True)\n
['Python3']