Python BFS + DFS Bit Mask
Intuition\n\nPS : I am writing this for myself.\n\n### Observation 1: \nWe have to check all posible moves for each turn of Alices or Bob, for that we use \nBIT
# Intuition\n\nPS : I am writing this for myself.\n\n### Observation 1: \nWe have to check all posible moves for each turn of Alices or Bob, for that we use \n**BIT-Mask DP and DFS** to explore each path and get the maximum number of moves. \n\n### Observation 2: \nWe need to efficiently find the distance between each position to other positions, and we precalculate this using **BFS**. \n\nThansk @votrubac for explaining this solution very well. \n\n\n\n\n# Complexity\n- Time complexity:\n- $$O(n)$$ for BFS \n- $$O(n*n)$$ for DFS\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- $$O(500)$$ for moves \n- $$O(n*n)$$ for  dp \n\n\n# Code\n```python3 []\nknight_moves = [\n            (2, 1),  (2, -1),  # Two steps vertically, one step horizontally\n            (-2, 1), (-2, -1), # Two steps vertically, one step horizontally (opposite)\n            (1, 2),  (1, -2),  # Two steps horizontally, one step vertically\n            (-1, 2), (-1, -2)  # Two steps horizontally, one step vertically (opposite)\n        ]\n\n\n\nclass Solution:\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n\n        pawns = set()\n        \n        positions.append((kx,ky))\n        res = 0\n        sz = len(positions)\n\n        moves = [[0 for i in range(sz)] for i in range(sz)]\n\n        def bfs(i):\n            d = [[0 for i in range(50)] for i in range(50)]\n            cx,cy = positions[i]\n            queue = deque([(cx,cy)])\n            while queue:\n                second_queue = deque([])\n                for xi,yi in queue:\n                    for dx,dy in knight_moves:\n                        x,y = xi + dx , yi + dy \n                        if 0 <= x < 50 and 0 <= y < 50 and \\\n                        not (x == cx and y == cy) and d[x][y] == 0:\n                            d[x][y] = d[xi][yi] + 1 \n                            second_queue.append((x,y))\n                queue = second_queue\n            \n            for j in range(i + 1, len(positions)):\n                moves[i][j] = moves[j][i] = d[positions[j][0]][positions[j][1]]\n        \n        for i in range(len(positions)):\n            bfs(i)\n\n            \n\n        dp = collections.defaultdict(lambda : -1)\n        def dfs(idx,mask,turns):\n            # print(positions[idx],bin(mask)[2:],turns)\n            if turns == sz - 1:\n                return 0 \n            if dp[(idx,mask)] != -1:\n                return dp[(idx,mask)]\n            \n            if turns%2 == 0:\n                # alice\'s turn\n                res = 0\n                for pos in range(sz-1):\n                    if mask & (1 << pos) == 0:\n                        # cx,cy = positions[idx]\n                        # tx,ty = positions[pos]\n                        curr = moves[idx][pos] + dfs(pos, mask | (1 << pos), turns + 1)\n                        res = max(res, curr)\n\n            else:\n                # bob\'s turn\n                res = float("inf")\n                for pos in range(sz-1):\n                    if mask & (1 << pos) == 0:\n                        # cx,cy = positions[idx]\n                        # tx,ty = positions[pos]\n                        curr = moves[idx][pos] + dfs(pos, mask | (1 << pos), turns + 1)\n                        res = min(res, curr)\n            dp[(idx,mask)] = res \n            return res \n        \n        return dfs(sz - 1 , 0, 0)\n        \n\n        \n```
['Python3']