fork download
copy 
  1. from typing import List
  2.  
  3. class Solution:
  4.     def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
  5.         from collections import deque
  6.         from functools import lru_cache
  7.  
  8.         n = len(positions)
  9.         positions = [[kx, ky]] + positions  # positions[0] is the knight's starting position
  10.  
  11.         # Precompute the minimum number of knight moves between all pairs of positions
  12.         dist = [[0] * (n + 1) for _ in range(n + 1)]
  13.  
  14.         def knight_moves(start_x, start_y):
  15.             moves = [(-2, -1), (-1, -2), (-2, 1), (-1, 2),
  16.                      (2, -1), (1, -2), (2, 1), (1, 2)]
  17.             dist_map = {}
  18.             queue = deque()
  19.             queue.append((start_x, start_y))
  20.             dist_map[(start_x, start_y)] = 0
  21.             while queue:
  22.                 x, y = queue.popleft()
  23.                 for dx, dy in moves:
  24.                     nx, ny = x + dx, y + dy
  25.                     if 0 <= nx < 50 and 0 <= ny < 50 and (nx, ny) not in dist_map:
  26.                         dist_map[(nx, ny)] = dist_map[(x, y)] + 1
  27.                         queue.append((nx, ny))
  28.             return dist_map
  29.  
  30.         # Compute distances from each position to every other position
  31.         for i in range(n + 1):
  32.             start_x, start_y = positions[i]
  33.             dist_map = knight_moves(start_x, start_y)
  34.             for j in range(n + 1):
  35.                 end_x, end_y = positions[j]
  36.                 dist[i][j] = dist_map.get((end_x, end_y), float('inf'))
  37.  
  38.         @lru_cache(None)
  39.         def dfs(curr_pos_index, remaining_pawns_bitmask, isAliceTurn):
  40.             if remaining_pawns_bitmask == 0:
  41.                 return 0
  42.             if isAliceTurn:
  43.                 max_total_moves = float('-inf')
  44.                 for i in range(1, n + 1):
  45.                     if remaining_pawns_bitmask & (1 << (i - 1)):
  46.                         new_bitmask = remaining_pawns_bitmask ^ (1 << (i - 1))
  47.                         total_moves = dist[curr_pos_index][i] + dfs(i, new_bitmask, False)
  48.                         max_total_moves = max(max_total_moves, total_moves)
  49.                 return max_total_moves
  50.             else:
  51.                 min_total_moves = float('inf')
  52.                 for i in range(1, n + 1):
  53.                     if remaining_pawns_bitmask & (1 << (i - 1)):
  54.                         new_bitmask = remaining_pawns_bitmask ^ (1 << (i - 1))
  55.                         total_moves = dist[curr_pos_index][i] + dfs(i, new_bitmask, True)
  56.                         min_total_moves = min(min_total_moves, total_moves)
  57.                 return min_total_moves
  58.  
  59.         remaining_pawns_bitmask = (1 << n) - 1  # All pawns are initially on the board
  60.         return dfs(0, remaining_pawns_bitmask, True)
  61.  
Success #stdin #stdout 0.03s 9680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/42FEf7
language:
Python 3 (python  3.9.5)
created:
39 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!