BFS + dp + bitmask
\n\n# Code\npython3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        positions = [[kx,ky]] + positions
\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        positions = [[kx,ky]] + positions\n        posdict = {(x,y):i for i,(x,y) in enumerate(positions)}\n        N = len(positions)\n        distances = [[None for i in range(N)] for j in range(N)]\n        for px,py in positions:\n            queue = [(px,py,0)]\n            seen = set([(px,py)])\n            for x,y,d in queue:\n                if (x,y) in posdict:\n                    distances[posdict[(px,py)]][posdict[(x,y)]] = d\n                for dx,dy in [(2,1),(1,2),(2,-1),(1,-2),(-1,2),(-2,1),(-2,-1),(-1,-2)]:\n                    if 0<=x+dx<50 and 0<=y+dy<50 and (x+dx,y+dy) not in seen:\n                        queue.append((x+dx,y+dy,d+1))\n                        seen.add((x+dx,y+dy))\n        @cache\n        def dp(i,mask,turn):\n            if mask == 2**N - 1:\n                return 0\n            if turn == 0:\n                res = -inf\n            else:\n                res = inf\n            for j in range(N):\n                if mask & (1<<j) == 0:\n                    if turn == 0:\n                        res = max(res,distances[i][j]+dp(j,mask|(1<<j),1))\n                    else:\n                        res = min(res,distances[i][j]+dp(j,mask|(1<<j),0))\n            return res\n        return dp(0,1,0)\n\n        \n```
['Breadth-First Search', 'Bitmask', 'Python3']