from typing import List
class Solution:
def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
from collections import deque
from functools import lru_cache
n = len(positions)
positions = [[kx, ky]] + positions # positions[0] is the knight's starting position
# Precompute the minimum number of knight moves between all pairs of positions
dist = [[0] * (n + 1) for _ in range(n + 1)]
def knight_moves(start_x, start_y):
moves = [(-2, -1), (-1, -2), (-2, 1), (-1, 2),
(2, -1), (1, -2), (2, 1), (1, 2)]
dist_map = {}
queue = deque()
queue.append((start_x, start_y))
dist_map[(start_x, start_y)] = 0
while queue:
x, y = queue.popleft()
for dx, dy in moves:
nx, ny = x + dx, y + dy
if 0 <= nx < 50 and 0 <= ny < 50 and (nx, ny) not in dist_map:
dist_map[(nx, ny)] = dist_map[(x, y)] + 1
queue.append((nx, ny))
return dist_map
# Compute distances from each position to every other position
for i in range(n + 1):
start_x, start_y = positions[i]
dist_map = knight_moves(start_x, start_y)
for j in range(n + 1):
end_x, end_y = positions[j]
dist[i][j] = dist_map.get((end_x, end_y), float('inf'))
@lru_cache(None)
def dfs(curr_pos_index, remaining_pawns_bitmask, isAliceTurn):
if remaining_pawns_bitmask == 0:
return 0
if isAliceTurn:
max_total_moves = float('-inf')
for i in range(1, n + 1):
if remaining_pawns_bitmask & (1 << (i - 1)):
new_bitmask = remaining_pawns_bitmask ^ (1 << (i - 1))
total_moves = dist[curr_pos_index][i] + dfs(i, new_bitmask, False)
max_total_moves = max(max_total_moves, total_moves)
return max_total_moves
else:
min_total_moves = float('inf')
for i in range(1, n + 1):
if remaining_pawns_bitmask & (1 << (i - 1)):
new_bitmask = remaining_pawns_bitmask ^ (1 << (i - 1))
total_moves = dist[curr_pos_index][i] + dfs(i, new_bitmask, True)
min_total_moves = min(min_total_moves, total_moves)
return min_total_moves
remaining_pawns_bitmask = (1 << n) - 1 # All pawns are initially on the board
return dfs(0, remaining_pawns_bitmask, True)
ZnJvbSB0eXBpbmcgaW1wb3J0IExpc3QKCmNsYXNzIFNvbHV0aW9uOgogICAgZGVmIG1heE1vdmVzKHNlbGYsIGt4OiBpbnQsIGt5OiBpbnQsIHBvc2l0aW9uczogTGlzdFtMaXN0W2ludF1dKSAtPiBpbnQ6CiAgICAgICAgZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKICAgICAgICBmcm9tIGZ1bmN0b29scyBpbXBvcnQgbHJ1X2NhY2hlCiAgICAgICAgCiAgICAgICAgbiA9IGxlbihwb3NpdGlvbnMpCiAgICAgICAgcG9zaXRpb25zID0gW1treCwga3ldXSArIHBvc2l0aW9ucyAgIyBwb3NpdGlvbnNbMF0gaXMgdGhlIGtuaWdodCdzIHN0YXJ0aW5nIHBvc2l0aW9uCiAgICAgICAgCiAgICAgICAgIyBQcmVjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBrbmlnaHQgbW92ZXMgYmV0d2VlbiBhbGwgcGFpcnMgb2YgcG9zaXRpb25zCiAgICAgICAgZGlzdCA9IFtbMF0gKiAobiArIDEpIGZvciBfIGluIHJhbmdlKG4gKyAxKV0KICAgICAgICAKICAgICAgICBkZWYga25pZ2h0X21vdmVzKHN0YXJ0X3gsIHN0YXJ0X3kpOgogICAgICAgICAgICBtb3ZlcyA9IFsoLTIsIC0xKSwgKC0xLCAtMiksICgtMiwgMSksICgtMSwgMiksCiAgICAgICAgICAgICAgICAgICAgICgyLCAtMSksICgxLCAtMiksICgyLCAxKSwgKDEsIDIpXQogICAgICAgICAgICBkaXN0X21hcCA9IHt9CiAgICAgICAgICAgIHF1ZXVlID0gZGVxdWUoKQogICAgICAgICAgICBxdWV1ZS5hcHBlbmQoKHN0YXJ0X3gsIHN0YXJ0X3kpKQogICAgICAgICAgICBkaXN0X21hcFsoc3RhcnRfeCwgc3RhcnRfeSldID0gMAogICAgICAgICAgICB3aGlsZSBxdWV1ZToKICAgICAgICAgICAgICAgIHgsIHkgPSBxdWV1ZS5wb3BsZWZ0KCkKICAgICAgICAgICAgICAgIGZvciBkeCwgZHkgaW4gbW92ZXM6CiAgICAgICAgICAgICAgICAgICAgbngsIG55ID0geCArIGR4LCB5ICsgZHkKICAgICAgICAgICAgICAgICAgICBpZiAwIDw9IG54IDwgNTAgYW5kIDAgPD0gbnkgPCA1MCBhbmQgKG54LCBueSkgbm90IGluIGRpc3RfbWFwOgogICAgICAgICAgICAgICAgICAgICAgICBkaXN0X21hcFsobngsIG55KV0gPSBkaXN0X21hcFsoeCwgeSldICsgMQogICAgICAgICAgICAgICAgICAgICAgICBxdWV1ZS5hcHBlbmQoKG54LCBueSkpCiAgICAgICAgICAgIHJldHVybiBkaXN0X21hcAogICAgICAgIAogICAgICAgICMgQ29tcHV0ZSBkaXN0YW5jZXMgZnJvbSBlYWNoIHBvc2l0aW9uIHRvIGV2ZXJ5IG90aGVyIHBvc2l0aW9uCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobiArIDEpOgogICAgICAgICAgICBzdGFydF94LCBzdGFydF95ID0gcG9zaXRpb25zW2ldCiAgICAgICAgICAgIGRpc3RfbWFwID0ga25pZ2h0X21vdmVzKHN0YXJ0X3gsIHN0YXJ0X3kpCiAgICAgICAgICAgIGZvciBqIGluIHJhbmdlKG4gKyAxKToKICAgICAgICAgICAgICAgIGVuZF94LCBlbmRfeSA9IHBvc2l0aW9uc1tqXQogICAgICAgICAgICAgICAgZGlzdFtpXVtqXSA9IGRpc3RfbWFwLmdldCgoZW5kX3gsIGVuZF95KSwgZmxvYXQoJ2luZicpKQogICAgICAgIAogICAgICAgIEBscnVfY2FjaGUoTm9uZSkKICAgICAgICBkZWYgZGZzKGN1cnJfcG9zX2luZGV4LCByZW1haW5pbmdfcGF3bnNfYml0bWFzaywgaXNBbGljZVR1cm4pOgogICAgICAgICAgICBpZiByZW1haW5pbmdfcGF3bnNfYml0bWFzayA9PSAwOgogICAgICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICAgICAgaWYgaXNBbGljZVR1cm46CiAgICAgICAgICAgICAgICBtYXhfdG90YWxfbW92ZXMgPSBmbG9hdCgnLWluZicpCiAgICAgICAgICAgICAgICBmb3IgaSBpbiByYW5nZSgxLCBuICsgMSk6CiAgICAgICAgICAgICAgICAgICAgaWYgcmVtYWluaW5nX3Bhd25zX2JpdG1hc2sgJiAoMSA8PCAoaSAtIDEpKToKICAgICAgICAgICAgICAgICAgICAgICAgbmV3X2JpdG1hc2sgPSByZW1haW5pbmdfcGF3bnNfYml0bWFzayBeICgxIDw8IChpIC0gMSkpCiAgICAgICAgICAgICAgICAgICAgICAgIHRvdGFsX21vdmVzID0gZGlzdFtjdXJyX3Bvc19pbmRleF1baV0gKyBkZnMoaSwgbmV3X2JpdG1hc2ssIEZhbHNlKQogICAgICAgICAgICAgICAgICAgICAgICBtYXhfdG90YWxfbW92ZXMgPSBtYXgobWF4X3RvdGFsX21vdmVzLCB0b3RhbF9tb3ZlcykKICAgICAgICAgICAgICAgIHJldHVybiBtYXhfdG90YWxfbW92ZXMKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIG1pbl90b3RhbF9tb3ZlcyA9IGZsb2F0KCdpbmYnKQogICAgICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UoMSwgbiArIDEpOgogICAgICAgICAgICAgICAgICAgIGlmIHJlbWFpbmluZ19wYXduc19iaXRtYXNrICYgKDEgPDwgKGkgLSAxKSk6CiAgICAgICAgICAgICAgICAgICAgICAgIG5ld19iaXRtYXNrID0gcmVtYWluaW5nX3Bhd25zX2JpdG1hc2sgXiAoMSA8PCAoaSAtIDEpKQogICAgICAgICAgICAgICAgICAgICAgICB0b3RhbF9tb3ZlcyA9IGRpc3RbY3Vycl9wb3NfaW5kZXhdW2ldICsgZGZzKGksIG5ld19iaXRtYXNrLCBUcnVlKQogICAgICAgICAgICAgICAgICAgICAgICBtaW5fdG90YWxfbW92ZXMgPSBtaW4obWluX3RvdGFsX21vdmVzLCB0b3RhbF9tb3ZlcykKICAgICAgICAgICAgICAgIHJldHVybiBtaW5fdG90YWxfbW92ZXMKICAgICAgICAKICAgICAgICByZW1haW5pbmdfcGF3bnNfYml0bWFzayA9ICgxIDw8IG4pIC0gMSAgIyBBbGwgcGF3bnMgYXJlIGluaXRpYWxseSBvbiB0aGUgYm9hcmQKICAgICAgICByZXR1cm4gZGZzKDAsIHJlbWFpbmluZ19wYXduc19iaXRtYXNrLCBUcnVlKQo=