Simple python3 solution | BFS + Bitmask + DP
Complexity\n- Time complexity: O(n \cdot m^2 + 2^n \cdot n^2)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n^2 + 2^n \cdot n)\n Add your
# Complexity\n- Time complexity: $$O(n \\cdot m^2 + 2^n \\cdot n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2 + 2^n \\cdot n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nwhere\n\n`n = positions.length <= 15`\n`m = 50`\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        m = 50\n        n = len(positions)\n\n        def get_distances(positions):\n            pos_to_index = {\n                (x, y): i\n                for i, (x, y) in enumerate(positions)\n            }\n            dxdy = (\n                (1, 2), (1, -2),\n                (-1, 2), (-1, -2),\n                (2, 1), (2, -1),\n                (-2, 1), (-2, -1),\n            )\n\n            def bfs(x, y):\n                dist = {}\n                queue = deque()\n                queue.append((0, x, y))\n                in_progress = {(x, y)}\n                while queue and len(dist) <= n:\n                    d, x, y = queue.popleft()\n                    if (new_index := pos_to_index.get((x, y))) is not None:\n                        dist[new_index] = d\n                    for dx, dy in dxdy:\n                        u = x + dx\n                        v = y + dy\n                        if (\n                            0 <= u < m and 0 <= v < m\n                            and (u, v) not in in_progress\n                        ):\n                            in_progress.add((u, v))\n                            queue.append((d + 1, u, v))\n                return dist\n\n            return {\n                i: bfs(x, y)\n                for i, (x, y) in enumerate(positions)\n            }\n        \n        positions.append((kx, ky))\n        dist = get_distances(positions)\n        positions.pop()\n\n        def get_indexes(bitmask):\n            bit = 1\n            value = 0\n            while bitmask >= bit:\n                if bitmask & bit:\n                    yield value\n                bit <<= 1\n                value += 1\n\n        @cache\n        def dp(bitmask, prev_index, is_alice):\n            if bitmask == 0:\n                return 0\n\n            func = max if is_alice else min\n            next_is_alice = not is_alice\n            return func(\n                (\n                    dp(bitmask ^ (1 << index), index, next_is_alice)\n                    + dist[prev_index][index]\n                )\n                for index in get_indexes(bitmask)\n            )\n\n        bitmask = (1 << n) - 1\n        return dp(bitmask, n, 1)\n```
['Dynamic Programming', 'Breadth-First Search', 'Bitmask', 'Python3']