Python | Clean Solution
Code\npython3 []\nfrom collections import deque\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n\n        # Dire
# Code\n```python3 []\nfrom collections import deque\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n\n        # Directions in which knight can move\n        directions = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]\n\n        # I have used a memory to store all the distances from each pawn to every other pawn as well as from knight\n        memory = {}\n        positions.append([kx,ky])\n\n        # Used BFS to calculate and fill \'memory\'\n        for x,y in positions:\n            visited = [[False for _ in range(50)] for _ in range(50)]\n            queue = deque()\n            queue.append((x,y,0))\n            visited[x][y] = True\n            while queue:\n                curr_x, curr_y, dist = queue.popleft()\n                memory[(x,y,curr_x,curr_y)] = dist\n                for move_x, move_y in directions:\n                    new_x = curr_x + move_x\n                    new_y = curr_y + move_y\n                    if new_x < 0 or new_x > 49 or new_y < 0 or new_y > 49:\n                        continue\n                    if visited[new_x][new_y]:\n                        continue\n                    queue.append((new_x, new_y, dist+1))\n                    visited[new_x][new_y] = True\n        \n        positions.pop()\n        dp = {}\n        n = len(positions)\n\n        # Bitmask to store if each pawn is visited or not (1 stands for not visited)\n        bitmask = tuple([1]*n)\n\n        # This function alternates Turns and computes maximum possible moves\n        def maximize(curr_x, curr_y, pawns, isAlice):\n\n            if 1 not in pawns:\n                return 0 # If all Pawns are visited\n\n            if (curr_x, curr_y, pawns, isAlice) in dp:\n                return dp[(curr_x, curr_y, pawns, isAlice)] # If current state has already occurred\n\n            if isAlice:\n                maxi = 0\n            else:\n                maxi = float(\'inf\')\n\n            pawns = list(pawns)\n\n            # kill each remaining pawn one by one and only take the one that gives maximum moves\n            for index, i in enumerate(pawns):\n                if i == 1:\n                    pawns[index] = 0\n                    target_x, target_y = positions[index]\n                    if isAlice:\n                        maxi = max(maxi, memory.get((curr_x, curr_y, target_x, target_y)) + maximize(target_x, target_y, tuple(pawns), not isAlice))\n                    else:\n                        maxi = min(maxi, memory.get((curr_x, curr_y, target_x, target_y)) + maximize(target_x, target_y, tuple(pawns), not isAlice))\n                    pawns[index] = 1\n\n            pawns = tuple(pawns)\n            dp[(curr_x, curr_y, pawns, isAlice)] = maxi\n            return maxi\n\n        return maximize(kx,ky,bitmask,True)\n                            \n\n\n\n```
['Dynamic Programming', 'Breadth-First Search', 'Python3']