[Python] Mask DP
Let $(p, q)$ be the minimum knight distance from points $p$ to $q$.  We can calculate it with BFS.\n\nLet dp[mask][u] be the remaining score if we play the game
Let $(p, q)$ be the minimum knight distance from points $p$ to $q$.  We can calculate it with BFS.\n\nLet `dp[mask][u]` be the remaining score if we play the game where pawns represented by set bits of `mask` have been captured already and the knight is at the `u`th pawn location.\n\nLet\'s now calculate the `dp` in reverse order of the game.  For every gamestate where the knight is at v, let\'s update with traveling from u to v.  At the end we have to also consider the original position of the knight traveling to the first pawn.\n\n# Code\n```python3 []\nN = 50\ndist = [[[[-1]*N for i in range(N)] for j in range(N)] for k in range(N)]\n\nfor x1, y1 in product(range(N), repeat=2):\n    queue = [[x1, y1, 0]]\n    dist[x1][y1][x1][y1] = 0\n    for x, y, d in queue:\n        for nx, ny in [[x-2,y+1],[x-2,y-1],[x-1,y+2],[x-1,y-2],\n                       [x+2,y+1],[x+2,y-1],[x+1,y+2],[x+1,y-2]\n            ]:\n            \n            if 0 <= nx < N and 0 <= ny < N and dist[x1][y1][nx][ny] == -1:\n                dist[x1][y1][nx][ny] = d + 1\n                queue.append([nx, ny, d + 1])\n\n\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, A: List[List[int]]) -> int:\n        N = len(A)\n\n        dp = [[0] * N for _ in range(1 << N)]\n        for mask in range((1 << N) - 1):\n            count = bin(mask).count("1")\n            dp[mask] = [(inf if count % 2 else -inf)] * N\n\n        for mask in range(1, 1 << N)[::-1]:\n            bits = [i for i in range(N) if mask >> i & 1]\n            fn = max if len(bits) % 2 else min\n            for u, v in permutations(bits, 2):\n                xu, yu, xv, yv = *A[u], *A[v]\n                pmask = mask ^ (1 << v)\n                dp[pmask][u] = fn(dp[pmask][u], dp[mask][v] + dist[xu][yu][xv][yv])\n\n        return max(dist[kx][ky][x][y] + dp[1 << u][u] for u, (x, y) in enumerate(A))\n```
['Python3']