Top Down DP| Python3
Approach\nCompute distances to all points from kx,ky and from each of positions.\nDP for bitmask states.\nDP(alice_move,x,y,mask)= max/min moves depending on al
# Approach\nCompute distances to all points from kx,ky and from each of positions.\nDP for bitmask states.\nDP(alice_move,x,y,mask)= max/min moves depending on alice/bob turn, to traverse unvisited(0 bit in mask) positons.\n\n# Complexity\n- Time complexity:\nO(n * 2^n )\n\n- Space complexity:\nO(n * 2^n )\n\n# Code\n```python3 []\nmoves = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]\n\n@cache\ndef get_mat(x,y):\n    d = [[-1] * 50 for _ in range(50)]\n    d[x][y] = 0\n    q = deque([(x, y)])\n    c = 0\n    while q:\n        c += 1\n        for _ in range(len(q)):\n            x, y = q.popleft()\n            for dx, dy in moves:\n                xx = x + dx\n                yy = y + dy\n                if 0 <= xx < 50 and 0 <= yy < 50 and d[xx][yy] == -1:\n                    d[xx][yy] = c\n                    q.append((xx, yy))\n    return d\n\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        n = len(positions)\n        @cache\n        def dists(x, y):\n            d=get_mat(x,y)\n            return [d[px][py] for px, py in positions]\n\n        @cache\n        def dp(alice,x,y,mask=0):\n            if mask.bit_count()==n:\n                return 0\n            cur = dists(x, y)\n            ans=-inf if alice else inf\n            for i in range(n):\n                if mask & (1 << i) == 0:\n                    px, py = positions[i]\n                    moves = cur[i] + dp(not alice, px, py, mask | (1 << i))\n                    if alice:\n                        ans = max(ans, moves)\n                    else:\n                        ans = min(ans,moves)\n            return ans\n        return dp(True, kx, ky)\n```
['Python3']