<p>There is a <code>50 x 50</code> chessboard with <strong>one</strong> knight and some pawns on it. You are given two integers <code>kx</code> and <code>ky</code> where <code>(kx, ky)</code> denotes the position of the knight, and a 2D array <code>positions</code> where <code>positions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> denotes the position of the pawns on the chessboard.</p>

<p>Alice and Bob play a <em>turn-based</em> game, where Alice goes first. In each player&#39;s turn:</p>

<ul>
	<li>The player <em>selects </em>a pawn that still exists on the board and captures it with the knight in the <strong>fewest</strong> possible <strong>moves</strong>. <strong>Note</strong> that the player can select <strong>any</strong> pawn, it <strong>might not</strong> be one that can be captured in the <strong>least</strong> number of moves.</li>
	<li><span>In the process of capturing the <em>selected</em> pawn, the knight <strong>may</strong> pass other pawns <strong>without</strong> capturing them</span>. <strong>Only</strong> the <em>selected</em> pawn can be captured in <em>this</em> turn.</li>
</ul>

<p>Alice is trying to <strong>maximize</strong> the <strong>sum</strong> of the number of moves made by <em>both</em> players until there are no more pawns on the board, whereas Bob tries to <strong>minimize</strong> them.</p>

<p>Return the <strong>maximum</strong> <em>total</em> number of moves made during the game that Alice can achieve, assuming both players play <strong>optimally</strong>.</p>

<p>Note that in one <strong>move, </strong>a chess knight has eight possible positions it can move to, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.</p>

<p><img src="https://assets.leetcode.com/uploads/2024/08/01/chess_knight.jpg" style="width: 275px; height: 273px;" /></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 1, ky = 1, positions = [[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/16/gif3.gif" style="width: 275px; height: 275px;" /></p>

<p>The knight takes 4 moves to reach the pawn at <code>(0, 0)</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">8</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/08/16/gif4.gif" style="width: 320px; height: 320px;" /></strong></p>

<ul>
	<li>Alice picks the pawn at <code>(2, 2)</code> and captures it in two moves: <code>(0, 2) -&gt; (1, 4) -&gt; (2, 2)</code>.</li>
	<li>Bob picks the pawn at <code>(3, 3)</code> and captures it in two moves: <code>(2, 2) -&gt; (4, 1) -&gt; (3, 3)</code>.</li>
	<li>Alice picks the pawn at <code>(1, 1)</code> and captures it in four moves: <code>(3, 3) -&gt; (4, 1) -&gt; (2, 2) -&gt; (0, 3) -&gt; (1, 1)</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">kx = 0, ky = 0, positions = [[1,2],[2,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Alice picks the pawn at <code>(2, 4)</code> and captures it in two moves: <code>(0, 0) -&gt; (1, 2) -&gt; (2, 4)</code>. Note that the pawn at <code>(1, 2)</code> is not captured.</li>
	<li>Bob picks the pawn at <code>(1, 2)</code> and captures it in one move: <code>(2, 4) -&gt; (1, 2)</code>.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= kx, ky &lt;= 49</code></li>
	<li><code>1 &lt;= positions.length &lt;= 15</code></li>
	<li><code>positions[i].length == 2</code></li>
	<li><code>0 &lt;= positions[i][0], positions[i][1] &lt;= 49</code></li>
	<li>All <code>positions[i]</code> are unique.</li>
	<li>The input is generated such that <code>positions[i] != [kx, ky]</code> for all <code>0 &lt;= i &lt; positions.length</code>.</li>
</ul>

# Notes: Alice maximizes, Bob minimizes, but moves to catch a pawn are minimized.
# * 50 x 50 board, up to 15 pawns, all positions are unique.
# * Cannot create all board distancesm but can find distances between each point.

N = 50

def getAdjss(n):
    adjss = defaultdict(set)
    for i0 in range(n):
        for j0 in range(n):
            k0 = (i0, j0)
            for i1 in (i0 - 2, i0 - 1, i0 + 1, i0 + 2):
                if i1 < 0 or i1 >= n:
                    continue
                for j1 in (j0 - 2, j0 - 1, j0 + 1, j0 + 2):
                    if j1 < 0 or j1 >= n:
                        continue
                    if abs(i0 - i1) + abs(j0 - j1) != 3:
                        continue
                    k1 = (i1, j1)
                    adjss[k0].add(k1)
    return adjss

ADJSS = getAdjss(50)
                    


class Solution:
  def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
    # print(f'ppDist from (0, 1) to (3, 4) is {self.getPpDist((0, 1), (3, 4))}')
    
    ppDists = defaultdict(dict)
    origin = (kx, ky)
    self.ps = [(x, y) for x, y in positions]
    self.nP = nP = len(self.ps)
    for p in self.ps:
      ppDist = self.getPpDist(origin, p)
      ppDists[origin][p] = ppDist
      ppDists[p][origin] = ppDist
    for i in range(nP):
      p0 = self.ps[i]
      for j in range(i + 1, nP):
        p1 = self.ps[j]
        ppDist = self.getPpDist(p0, p1)
        ppDists[p0][p1] = ppDist
        ppDists[p1][p0] = ppDist
    self.ppDists = ppDists
    board = self.getBoardFromIdxs(range(self.nP))
    # print(f'board={board}')
    return self.getAliceBest(origin, board)

  def getBoardFromIdxs(self, idxs):
    chs = ['0'] * self.nP
    for idx in idxs:
      chs[idx] = '1'
    return ''.join(chs)

  def getIdxsFromBoard(self, board):
    idxs = []
    for idx in range(self.nP):
      if board[idx] == '1':
        idxs.append(idx)
    return idxs
    

  @functools.cache
  def getBobBest(self, p, board):
    # Minimize.
    idxs = self.getIdxsFromBoard(board)
    if len(idxs) == 0:
      return 0
    bobBest = math.inf
    for idx1 in idxs:
      idxs2 = [idx2 for idx2 in idxs if idx2 != idx1]
      p1 = self.ps[idx1]
      board1 = self.getBoardFromIdxs(idxs2)
      bobVal = self.ppDists[p][p1] + self.getAliceBest(p1, board1)
      bobBest = min(bobBest, bobVal)
    # print(f'getBobBest({p}, {board}) = {bobBest}')
    return bobBest

  @functools.cache
  def getAliceBest(self, p, board):
    # Maximize.
    idxs = self.getIdxsFromBoard(board)
    if len(idxs) == 0:
      return 0
    aliceBest = 0
    for idx1 in idxs:
      idxs2 = [idx2 for idx2 in idxs if idx2 != idx1]
      p1 = self.ps[idx1]
      board1 = self.getBoardFromIdxs(idxs2)
      aliceVal = self.ppDists[p][p1] + self.getBobBest(p1, board1)
      # print(f'* p={p}, p1={p1}, aliceVal={aliceVal}')
      aliceBest = max(aliceBest, aliceVal)
    # print(f'getAliceBest({p}, {board}) = {aliceBest}')
    return aliceBest


  

      
  
  # Find dist from one pawn to another pawn.
  def getPpDist(self, p0, p1) -> int:
    nodes0 = [p0]
    visited = set(nodes0)
    dist = 0
    if p1 in visited:
      return 0
    while nodes0:
      dist += 1
      nodes1 = []
      for node0 in nodes0:
        for node1 in ADJSS[node0]:
          if node1 in visited:
            continue
          if node1 == p1:
            return dist
          nodes1.append(node1)
          visited.add(node1)
      nodes0 = nodes1
    raise ValueError('No path from {p0} to {p1}')


      

'''      
# ppDists holds dist from one pawn to another. How does minimax work?
# Cannot do 15 factorial. But can do 15 choose 7.

# Say there are 3 pawns and it is Alice's turn. Alice sees B's outcomes she
can maximize score given B's outcomes.


'''
173871