Problem

There is a 50 x 50 chessboard with one knight and some pawns on it. You are given two integers kx and ky where (kx, ky) denotes the position of the knight, and a 2D array positions where positions[i] = [xi, yi] denotes the position of the pawns on the chessboard.

Alice and Bob play a turn-based game, where Alice goes first. In each player’s turn:

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

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

Return the maximum total number of moves made during the game that Alice can achieve, assuming both players play optimally.

Note that in one move, 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: kx = 1, ky = 1, positions = [[0,0]]

Output: 4

Explanation:

![](https://assets.leetcode.com/uploads/2024/08/16/gif3.gif)

The knight takes 4 moves to reach the pawn at `(0, 0)`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]

Output: 8

Explanation:

**![](https://assets.leetcode.com/uploads/2024/08/16/gif4.gif)**

  * Alice picks the pawn at `(2, 2)` and captures it in two moves: `(0, 2) -> (1, 4) -> (2, 2)`.
  * Bob picks the pawn at `(3, 3)` and captures it in two moves: `(2, 2) -> (4, 1) -> (3, 3)`.
  * Alice picks the pawn at `(1, 1)` and captures it in four moves: `(3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1)`.

Example 3

1
2
3
4
5
6
7
8
9


Input: kx = 0, ky = 0, positions = [[1,2],[2,4]]

Output: 3

Explanation:

  * Alice picks the pawn at `(2, 4)` and captures it in two moves: `(0, 0) -> (1, 2) -> (2, 4)`. Note that the pawn at `(1, 2)` is not captured.
  * Bob picks the pawn at `(1, 2)` and captures it in one move: `(2, 4) -> (1, 2)`.

Constraints

  • 0 <= kx, ky <= 49
  • 1 <= positions.length <= 15
  • positions[i].length == 2
  • 0 <= positions[i][0], positions[i][1] <= 49
  • All positions[i] are unique.
  • The input is generated such that positions[i] != [kx, ky] for all 0 <= i < positions.length.

Solution

Method 1 – Minimax + BFS (Game Theory)

Intuition

This is a two-player minimax game where Alice tries to maximize and Bob tries to minimize the total number of moves. For each state (knight position, remaining pawns, turn), recursively try all possible pawn captures, using BFS to compute the minimum moves to each pawn, and alternate turns. Memoize states for efficiency.

Approach

  1. Use BFS to compute the minimum number of knight moves from the current position to each pawn.
  2. Use bitmask to represent the set of remaining pawns.
  3. Use minimax recursion: if it’s Alice’s turn, maximize the total moves; if Bob’s, minimize.
  4. Memoize the result for each (knight position, remaining pawns, turn).
  5. Try all possible next pawn captures for the current player.
  6. Return the optimal total moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <vector>
#include <queue>
#include <tuple>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        int n = positions.size();
        vector<pair<int, int>> pawns;
        for (auto& p : positions) pawns.emplace_back(p[0], p[1]);
        vector<vector<int>> dist(n+1, vector<int>(n, 0));
        auto bfs = [&](int sx, int sy) -> vector<int> {
            vector<vector<int>> d(50, vector<int>(50, -1));
            queue<pair<int, int>> q;
            q.emplace(sx, sy);
            d[sx][sy] = 0;
            vector<int> res(n);
            int dx[8] = {-2,-2,-1,-1,1,1,2,2}, dy[8] = {-1,1,-2,2,-2,2,-1,1};
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                for (int k = 0; k < 8; ++k) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.emplace(nx, ny);
                    }
                }
            }
            for (int i = 0; i < n; ++i) res[i] = d[pawns[i].first][pawns[i].second];
            return res;
        };
        dist[0] = bfs(kx, ky);
        for (int i = 0; i < n; ++i) dist[i+1] = bfs(pawns[i].first, pawns[i].second);
        unordered_map<long long, int> memo;
        function<int(int, int, int, bool)> dfs = [&](int pos, int mask, int turn, bool alice) -> int {
            long long key = ((long long)pos << 16) | (mask << 1) | alice;
            if (memo.count(key)) return memo[key];
            int best = alice ? -1e9 : 1e9;
            bool any = false;
            for (int i = 0; i < n; ++i) {
                if (!(mask & (1 << i))) continue;
                int d = dist[pos][i];
                if (d < 0) continue;
                any = true;
                int next = dfs(i+1, mask ^ (1 << i), turn+1, !alice) + d;
                if (alice) best = max(best, next);
                else best = min(best, next);
            }
            if (!any) return 0;
            return memo[key] = best;
        };
        return dfs(0, (1<<n)-1, 0, true);
    }
};
1

// Omitted for brevity, similar logic as C++ using BFS and memoized DFS with bitmask.
1

// Omitted for brevity, similar logic as C++ using BFS and memoized DFS with bitmask.
1

// Omitted for brevity, similar logic as C++ using BFS and memoized DFS with bitmask.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from collections import deque
from functools import cache
class Solution:
    def maxMoves(self, kx: int, ky: int, positions: list[list[int]]) -> int:
        n = len(positions)
        pawns = positions
        def bfs(sx, sy):
            d = [[-1]*50 for _ in range(50)]
            q = deque([(sx, sy)])
            d[sx][sy] = 0
            res = [0]*n
            dx = [-2,-2,-1,-1,1,1,2,2]
            dy = [-1,1,-2,2,-2,2,-1,1]
            while q:
                x, y = q.popleft()
                for k in range(8):
                    nx, ny = x+dx[k], y+dy[k]
                    if 0<=nx<50 and 0<=ny<50 and d[nx][ny]==-1:
                        d[nx][ny] = d[x][y]+1
                        q.append((nx, ny))
            for i in range(n):
                res[i] = d[pawns[i][0]][pawns[i][1]]
            return res
        dist = [bfs(kx, ky)] + [bfs(p[0], p[1]) for p in pawns]
        @cache
        def dfs(pos, mask, alice):
            best = -1e9 if alice else 1e9
            any_move = False
            for i in range(n):
                if not (mask & (1<<i)): continue
                d = dist[pos][i]
                if d < 0: continue
                any_move = True
                next_val = dfs(i+1, mask ^ (1<<i), not alice) + d
                if alice:
                    best = max(best, next_val)
                else:
                    best = min(best, next_val)
            if not any_move:
                return 0
            return best
        return dfs(0, (1<<n)-1, True)
1

// Omitted for brevity, similar logic as C++ using BFS and memoized DFS with bitmask.

1

// Omitted for brevity, similar logic as C++ using BFS and memoized DFS with bitmask.

Complexity

  • ⏰ Time complexity: O(n! * n^2), where n is the number of pawns (≤ 15), due to all permutations and BFS for each pawn.
  • 🧺 Space complexity: O(n * 2^n), for memoization and distance tables.