Bitmask DP + BFS
Intuition\nWhen you see the constraints are small, you should note that this is Bitmask DP.\n\n# Approach\nUse BFS to find out the shortest distance between paw
# Intuition\nWhen you see the constraints are small, you should note that this is ***Bitmask DP***.\n\n# Approach\nUse BFS to find out the shortest distance between pawn and knight.\nUse Bitmask DP to find out all possible stages of the board and it corresponding steps.\n\n# Complexity\n- Time complexity:\n$$O(2 * n * (n*2^n) + n ^2 * 50^2)$$\n2 is for Alice or Bob turn\nn is the length of pawn\n2^n is all the possible stages of the board will occur, each stage need to go through all n pawn. so total is n * 2^n\nn ^2 * 50^2 is the BFS to find the shortest distance for every pair of pawn\n\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        direction = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]\n        \n        @cache\n        def bfs(i, j, x, y):\n            queue = deque()\n            seen = set()\n            \n            queue.append((i, j))\n            seen.add((i, j))\n            \n            step = 0\n            while queue:\n                size = len(queue)\n                for _ in range(size):\n                    \n                    i, j = queue.popleft()\n                    \n                    if i == x and j == y:\n                        return step\n                    \n                    for d in direction:\n                        new_i, new_j = i + d[0], j + d[1]\n                        if 0 <= new_i < 50 and 0 <= new_j < 50 and (new_i, new_j) not in seen:\n                            queue.append((new_i, new_j))\n                            seen.add((new_i, new_j))\n                \n                step += 1\n\n        \n        n = len(positions)\n        @cache\n        def dfs(is_alice, ks, ky, stage):\n            if stage == (1 << n) - 1:\n                return 0\n            \n            if is_alice:\n                result = 0\n            else:\n                result = inf\n            \n            for next_pawn in range(n):\n                if stage & (1 << next_pawn) == 0:\n                    step = bfs(ks, ky, positions[next_pawn][0], positions[next_pawn][1])\n                    \n                    total = dfs(not is_alice, positions[next_pawn][0], positions[next_pawn][1], (stage | (1 << next_pawn)))\n                    \n                    if is_alice and total + step > result:\n                        result = total + step\n                    \n                    if not is_alice and total + step < result:\n                        result = total + step\n                        \n            return result\n        \n        result = dfs(True, kx, ky, 0)\n        dfs.cache_clear()\n        return result\n```
['Dynamic Programming', 'Bit Manipulation', 'Breadth-First Search', 'Bitmask', 'Python3']