[Python3] Game Theory + Bit Mask DP - Simple Solution
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```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        n = len(positions)\n        dist = [[0 for _ in range(n)] for _ in range(n + 1)]\n        positions.append([kx, ky])\n        def bfs(i: int) -> int:\n            dq = collections.deque([positions[i]])\n            seen = set()\n            step = 0\n            while dq:\n                l = len(dq)\n                for _ in range(l):\n                    x, y = dq.popleft()\n                    if [x, y] == positions[j]: return step\n                    for dx, dy in [(-2, -1), (-2, 1), (-1, -2), (-1, 2),\n                                   (1, -2), (1, 2), (2, -1), (2, 1)]:\n                        cx, cy = x + dx, y + dy\n                        if cx < 0 or cx > 49 or cy < 0 or cy > 49 or (cx, cy) in seen: continue\n                        dq.append([cx, cy])\n                        seen.add((cx, cy))\n                step += 1\n\n        for i in range(n + 1):\n            for j in range(n):\n                if i == j: continue\n                dist[i][j] = bfs(i)\n                \n        ops = [max, min]\n        init = [0, float("inf")]\n\n        @cache\n        def dp(i: int, mask: int, player: int) -> int:\n            if mask == (1 << n) - 1: return 0\n            ans = init[player]\n            for j in range(n):\n                if mask & (1 << j): continue\n                ans = ops[player](ans, dist[i][j] + dp(j, mask | (1 << j), player ^ 1))\n            return ans\n        return dp(n, 0, 0)\n```
['Dynamic Programming', 'Game Theory', 'Bitmask', 'Python3']