BEST PYTHON SOLUTION WITH 9544MS OF RUNTIME !
\n# Code\npython3 []\nfrom typing import List\nfrom collections import deque\nfrom functools import cache\nimport math\n\nclass Solution:\n    def maxMoves(self
\n# Code\n```python3 []\nfrom typing import List\nfrom collections import deque\nfrom functools import cache\nimport math\n\nclass Solution:\n    def maxMoves(self, start_x: int, start_y: int, positions: List[List[int]]) -> int:\n        num_positions = len(positions)\n        distance_matrix = [[0] * num_positions for _ in range(num_positions + 1)]\n        positions.append([start_x, start_y])\n        \n        for from_idx in range(num_positions + 1):\n            for to_idx in range(num_positions):\n                if from_idx != to_idx:\n                    queue = deque([positions[from_idx]])\n                    visited = set()\n                    steps = 0\n                    while queue:\n                        for _ in range(len(queue)):\n                            x, y = queue.popleft()\n                            if [x, y] == positions[to_idx]:\n                                distance_matrix[from_idx][to_idx] = steps\n                                break\n                            for dx, dy in [(-2, -1), (-2, 1), (-1, -2), (-1, 2),\n                                           (1, -2), (1, 2), (2, -1), (2, 1)]:\n                                nx, ny = x + dx, y + dy\n                                if 0 <= nx < 50 and 0 <= ny < 50 and (nx, ny) not in visited:\n                                    queue.append([nx, ny])\n                                    visited.add((nx, ny))\n                        else:\n                            steps += 1\n                            continue\n                        break\n        \n        operations = [max, min]\n        initial_values = [0, math.inf]\n        \n        @cache\n        def dp(current_idx: int, visited_mask: int, turn: int) -> int:\n            if visited_mask == (1 << num_positions) - 1:\n                return 0\n            \n            result = initial_values[turn]\n            for next_idx in range(num_positions):\n                if not visited_mask & (1 << next_idx):\n                    new_mask = visited_mask | (1 << next_idx)\n                    result = operations[turn](result, distance_matrix[current_idx][next_idx] + dp(next_idx, new_mask, turn ^ 1))\n            return result\n        \n        return dp(num_positions, 0, 0)\n\n```
['Python3']