[Python3] Bitset DP + BFS (min-max)
Intuition\n Describe your first thoughts on how to solve this problem. \n- Use a bitmask to encode the already captured pawns, then for choose from the set of u
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use a bitmask to encode the already captured pawns, then for choose from the set of uncaptured pawns the one that will ensure the maximum (Alice) or minimum (Bob) number of moves\n- BFS to find the minimum number of moves to capture a pawn, starting from the position of the knight\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        dx = [-2, -1, +1, +2, +2, +1, -1, -2]\n        dy = [+1, +2, +2, +1, -1, -2, -2, -1]\n        n = len(positions)\n\n        @cache\n        def capturePawn(kkx, kky, pos):\n            moves = 0\n\n            q = [[kkx, kky]]\n            vis = [[False for _ in range(50)] for _ in range(50)]\n            vis[kkx][kky] = True\n\n            while True:\n                ll = len(q)\n                for i in range(ll):\n                    current = q.pop(0)\n                    if current[0] == pos[0] and current[1] == pos[1]:\n                        return moves\n\n                    for j in range(8):\n                        nextX = current[0] + dx[j]\n                        nextY = current[1] + dy[j]\n\n                        if 0 <= nextX <= 49 and 0 <= nextY <= 49:\n                            if not vis[nextX][nextY]:\n                                vis[nextX][nextY] = True\n                                q.append([nextX, nextY])\n\n                moves += 1\n\n            # use bfs\n            return moves\n\n        fin = (1 << n) - 1\n\n        @cache\n        def dp(alice: bool, state: int, kkx, kky):\n            if state == fin:\n                return 0\n            score = -1\n\n            if alice:\n                # chose the option which gives the maximum sum of moves in the end\n                for i in range(n):\n                    if state & (1 << i) == 0:\n                        current = capturePawn(kkx, kky, tuple(positions[i]))\n\n                        if score == -1:\n                            score = current + dp(False, state | (1 << i), positions[i][0], positions[i][1])\n                        else:\n                            score = max(score, current + dp(False, state | (1 << i), positions[i][0], positions[i][1]))\n            else:\n                # chose the option which gives the minimum sum of moves in the end\n                for i in range(n):\n                    if state & (1 << i) == 0:\n                        current = capturePawn(kkx, kky, tuple(positions[i]))\n\n                        if score == -1:\n                            score = current + dp(True, state | (1 << i), positions[i][0], positions[i][1])\n                        else:\n                            score = min(score, current  + dp(True, state | (1 << i), positions[i][0], positions[i][1]))\n            return score\n\n        return dp(True, 0, kx, ky)\n\n```
['Python3']