Recursive DP and Dijkstra shortest path
Intuition\n\nIn Alice\'s turn we try to capture the existing pawns one by one and maximize the moves, while in Bob\'s turn we minimize the moves.\n\nDijkstra sh
# Intuition\n\nIn Alice\'s turn we try to capture the existing pawns one by one and maximize the moves, while in Bob\'s turn we minimize the moves.\n\nDijkstra shortest path can find the shortest path from the current knight position to every corner of the board.\n\nAnd we can take dynamic programming approach to reduce the exponential way of choosing subproblems.\n \n# Approach\n\nWe have a `calc` function that recursively calculates the moves of a player. Index of the captured pawns are kept as a bit-mask.\n\n- `calc` calculates the moves in each turn\n    - curx,cury is the x,y position of the knight\n    - step is the turn or recursion depth\n        - when `step == len(pawns)` that ends the algorithm\n    - captured is the bitmask of the captured pawn\n\nAgain we have `calcMovesShortest` which runs Dijkstra shortest path algorithm from knight position (knx,kny) to all the other positions in the board.\n\n# Complexity\n- Time complexity:\n\nO(2^15)\n\n- Space complexity:\n\nO(2^15)\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        INF = float(\'Inf\')\n        @cache\n        def calcMovesShortest(knx,kny):\n            board = [[INF]*50 for _ in range(50)]\n            \n            moves = [(0,knx,kny)]\n            board[knx][kny] = 0\n            while moves:\n                cost,x,y = heappop(moves)\n                if cost > board[x][y]:\n                    continue\n\n                # knight has 8 moves\n                for xpos in (x-2,x+2):\n                    if xpos >= 0 and xpos < 50:\n                        for ypos in (y-1,y+1):\n                            if ypos >= 0 and ypos < 50:\n                                if board[xpos][ypos] > (cost+1):\n                                    board[xpos][ypos] = cost+1\n                                    heappush(moves,(cost+1,xpos,ypos))\n                            \n                for xpos in (x-1,x+1):\n                    if xpos >= 0 and xpos < 50:\n                        for ypos in (y-2,y+2):\n                            if ypos >= 0 and ypos < 50:\n                                if board[xpos][ypos] > (cost+1):\n                                    board[xpos][ypos] = cost+1\n                                    heappush(moves,(cost+1,xpos,ypos))\n                            \n                            \n            return board\n        \n        NSTEP = len(positions)\n        pawns = positions[:]\n        \n        @cache\n        def calc(curx,cury, step, captured):\n            if NSTEP == step:\n                return 0\n\n            brd = calcMovesShortest(curx,cury)\n            table = []\n            for i in range(NSTEP):\n                if captured & (1<<i):\n                    continue\n                x,y = pawns[i]\n                table.append( (brd[x][y],i) )\n            \n            ret = INF if (step&1) else 0\n            for c,idx in table:\n                cap2 = captured | (1<<idx)\n                x,y = pawns[idx]\n                calccost = c+calc(x,y, step+1,cap2)\n                ret = min(ret,calccost) if (step&1) else max(ret,calccost)\n           \n            return ret\n                \n        return calc(kx,ky,0,0)\n```
['Python3']