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
  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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

func maxMoves(kx int, ky int, positions [][]int) int {
    n := len(positions)
    pawns := make([][2]int, n)
    for i, p := range positions {
        pawns[i] = [2]int{p[0], p[1]}
    }
    
    // Distance matrix: dist[i][j] = distance from position i to pawn j
    dist := make([][]int, n+1)
    for i := range dist {
        dist[i] = make([]int, n)
    }
    
    // BFS to compute minimum knight moves
    bfs := func(sx, sy int) []int {
        d := make([][]int, 50)
        for i := range d {
            d[i] = make([]int, 50)
            for j := range d[i] {
                d[i][j] = -1
            }
        }
        
        queue := [][2]int{{sx, sy}}
        d[sx][sy] = 0
        res := make([]int, n)
        
        dx := []int{-2, -2, -1, -1, 1, 1, 2, 2}
        dy := []int{-1, 1, -2, 2, -2, 2, -1, 1}
        
        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            x, y := curr[0], curr[1]
            
            for k := 0; k < 8; k++ {
                nx, ny := x+dx[k], y+dy[k]
                if nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1 {
                    d[nx][ny] = d[x][y] + 1
                    queue = append(queue, [2]int{nx, ny})
                }
            }
        }
        
        for i := 0; i < n; i++ {
            res[i] = d[pawns[i][0]][pawns[i][1]]
        }
        return res
    }
    
    // Compute distances from initial knight position and each pawn position
    dist[0] = bfs(kx, ky)
    for i := 0; i < n; i++ {
        dist[i+1] = bfs(pawns[i][0], pawns[i][1])
    }
    
    // Memoization map
    memo := make(map[int64]int)
    
    // DFS with memoization
    var dfs func(int, int, bool) int
    dfs = func(pos, mask int, alice bool) int {
        key := int64(pos)<<16 | int64(mask)<<1
        if alice {
            key |= 1
        }
        
        if val, exists := memo[key]; exists {
            return val
        }
        
        var best int
        if alice {
            best = -1e9
        } else {
            best = 1e9
        }
        
        anyMove := false
        for i := 0; i < n; i++ {
            if (mask & (1 << i)) == 0 {
                continue
            }
            d := dist[pos][i]
            if d < 0 {
                continue
            }
            anyMove = true
            nextVal := dfs(i+1, mask^(1<<i), !alice) + d
            if alice {
                best = max(best, nextVal)
            } else {
                best = min(best, nextVal)
            }
        }
        
        if !anyMove {
            memo[key] = 0
            return 0
        }
        
        memo[key] = best
        return best
    }
    
    return dfs(0, (1<<n)-1, true)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

import java.util.*;

class Solution {
    public int maxMoves(int kx, int ky, int[][] positions) {
        int n = positions.length;
        int[][] pawns = new int[n][2];
        for (int i = 0; i < n; i++) {
            pawns[i][0] = positions[i][0];
            pawns[i][1] = positions[i][1];
        }
        
        // Distance matrix: dist[i][j] = distance from position i to pawn j
        int[][] dist = new int[n + 1][n];
        
        // BFS to compute minimum knight moves
        int[] bfs(int sx, int sy) {
            int[][] d = new int[50][50];
            for (int i = 0; i < 50; i++) {
                Arrays.fill(d[i], -1);
            }
            
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{sx, sy});
            d[sx][sy] = 0;
            int[] res = new int[n];
            
            int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
            int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
            
            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                int x = curr[0], y = curr[1];
                
                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;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            
            for (int i = 0; i < n; i++) {
                res[i] = d[pawns[i][0]][pawns[i][1]];
            }
            return res;
        }
        
        // Compute distances from initial knight position and each pawn position
        dist[0] = bfs(kx, ky);
        for (int i = 0; i < n; i++) {
            dist[i + 1] = bfs(pawns[i][0], pawns[i][1]);
        }
        
        // Memoization map
        Map<Long, Integer> memo = new HashMap<>();
        
        return dfs(0, (1 << n) - 1, true, dist, memo, n);
    }
    
    private int dfs(int pos, int mask, boolean alice, int[][] dist, Map<Long, Integer> memo, int n) {
        long key = ((long) pos << 16) | (mask << 1L) | (alice ? 1L : 0L);
        
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int best = alice ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        boolean anyMove = false;
        
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            int d = dist[pos][i];
            if (d < 0) continue;
            anyMove = true;
            int nextVal = dfs(i + 1, mask ^ (1 << i), !alice, dist, memo, n) + d;
            if (alice) {
                best = Math.max(best, nextVal);
            } else {
                best = Math.min(best, nextVal);
            }
        }
        
        if (!anyMove) {
            memo.put(key, 0);
            return 0;
        }
        
        memo.put(key, best);
        return best;
    }
}
 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

import java.util.*
import kotlin.math.*

class Solution {
    fun maxMoves(kx: Int, ky: Int, positions: Array<IntArray>): Int {
        val n = positions.size
        val pawns = Array(n) { i -> intArrayOf(positions[i][0], positions[i][1]) }
        
        // Distance matrix: dist[i][j] = distance from position i to pawn j
        val dist = Array(n + 1) { IntArray(n) }
        
        // BFS to compute minimum knight moves
        fun bfs(sx: Int, sy: Int): IntArray {
            val d = Array(50) { IntArray(50) { -1 } }
            val queue: Queue<Pair<Int, Int>> = LinkedList()
            queue.offer(Pair(sx, sy))
            d[sx][sy] = 0
            val res = IntArray(n)
            
            val dx = intArrayOf(-2, -2, -1, -1, 1, 1, 2, 2)
            val dy = intArrayOf(-1, 1, -2, 2, -2, 2, -1, 1)
            
            while (queue.isNotEmpty()) {
                val (x, y) = queue.poll()
                
                for (k in 0 until 8) {
                    val nx = x + dx[k]
                    val ny = y + dy[k]
                    if (nx in 0 until 50 && ny in 0 until 50 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1
                        queue.offer(Pair(nx, ny))
                    }
                }
            }
            
            for (i in 0 until n) {
                res[i] = d[pawns[i][0]][pawns[i][1]]
            }
            return res
        }
        
        // Compute distances from initial knight position and each pawn position
        dist[0] = bfs(kx, ky)
        for (i in 0 until n) {
            dist[i + 1] = bfs(pawns[i][0], pawns[i][1])
        }
        
        // Memoization map
        val memo = mutableMapOf<Long, Int>()
        
        fun dfs(pos: Int, mask: Int, alice: Boolean): Int {
            val key = (pos.toLong() shl 16) or (mask.toLong() shl 1) or if (alice) 1L else 0L
            
            if (key in memo) {
                return memo[key]!!
            }
            
            var best = if (alice) Int.MIN_VALUE else Int.MAX_VALUE
            var anyMove = false
            
            for (i in 0 until n) {
                if ((mask and (1 shl i)) == 0) continue
                val d = dist[pos][i]
                if (d < 0) continue
                anyMove = true
                val nextVal = dfs(i + 1, mask xor (1 shl i), !alice) + d
                if (alice) {
                    best = max(best, nextVal)
                } else {
                    best = min(best, nextVal)
                }
            }
            
            if (!anyMove) {
                memo[key] = 0
                return 0
            }
            
            memo[key] = best
            return best
        }
        
        return dfs(0, (1 shl n) - 1, true)
    }
}
 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
 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {
        let n = positions.len();
        let pawns: Vec<(i32, i32)> = positions.iter().map(|p| (p[0], p[1])).collect();
        
        // Distance matrix: dist[i][j] = distance from position i to pawn j
        let mut dist = vec![vec![0; n]; n + 1];
        
        // BFS to compute minimum knight moves
        let bfs = |sx: i32, sy: i32| -> Vec<i32> {
            let mut d = vec![vec![-1; 50]; 50];
            let mut queue = VecDeque::new();
            queue.push_back((sx, sy));
            d[sx as usize][sy as usize] = 0;
            let mut res = vec![0; n];
            
            let dx = [-2, -2, -1, -1, 1, 1, 2, 2];
            let dy = [-1, 1, -2, 2, -2, 2, -1, 1];
            
            while let Some((x, y)) = queue.pop_front() {
                for k in 0..8 {
                    let nx = x + dx[k];
                    let ny = y + dy[k];
                    if nx >= 0 && nx < 50 && ny >= 0 && ny < 50 {
                        let (nx_u, ny_u) = (nx as usize, ny as usize);
                        if d[nx_u][ny_u] == -1 {
                            d[nx_u][ny_u] = d[x as usize][y as usize] + 1;
                            queue.push_back((nx, ny));
                        }
                    }
                }
            }
            
            for i in 0..n {
                res[i] = d[pawns[i].0 as usize][pawns[i].1 as usize];
            }
            res
        };
        
        // Compute distances from initial knight position and each pawn position
        dist[0] = bfs(kx, ky);
        for i in 0..n {
            dist[i + 1] = bfs(pawns[i].0, pawns[i].1);
        }
        
        // Memoization map
        let mut memo = HashMap::new();
        
        fn dfs(
            pos: usize,
            mask: i32,
            alice: bool,
            dist: &Vec<Vec<i32>>,
            memo: &mut HashMap<i64, i32>,
            n: usize,
        ) -> i32 {
            let key = ((pos as i64) << 16) | ((mask as i64) << 1) | if alice { 1 } else { 0 };
            
            if let Some(&val) = memo.get(&key) {
                return val;
            }
            
            let mut best = if alice { i32::MIN } else { i32::MAX };
            let mut any_move = false;
            
            for i in 0..n {
                if (mask & (1 << i)) == 0 {
                    continue;
                }
                let d = dist[pos][i];
                if d < 0 {
                    continue;
                }
                any_move = true;
                let next_val = dfs(i + 1, mask ^ (1 << i), !alice, dist, memo, n) + d;
                if alice {
                    best = best.max(next_val);
                } else {
                    best = best.min(next_val);
                }
            }
            
            if !any_move {
                memo.insert(key, 0);
                return 0;
            }
            
            memo.insert(key, best);
            best
        }
        
        dfs(0, (1 << n) - 1, true, &dist, &mut memo, n)
    }
}
 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

function maxMoves(kx: number, ky: number, positions: number[][]): number {
    const n = positions.length;
    const pawns: [number, number][] = positions.map(p => [p[0], p[1]]);
    
    // Distance matrix: dist[i][j] = distance from position i to pawn j
    const dist: number[][] = Array(n + 1).fill(null).map(() => Array(n).fill(0));
    
    // BFS to compute minimum knight moves
    const bfs = (sx: number, sy: number): number[] => {
        const d: number[][] = Array(50).fill(null).map(() => Array(50).fill(-1));
        const queue: [number, number][] = [[sx, sy]];
        d[sx][sy] = 0;
        const res: number[] = Array(n).fill(0);
        
        const dx = [-2, -2, -1, -1, 1, 1, 2, 2];
        const dy = [-1, 1, -2, 2, -2, 2, -1, 1];
        
        while (queue.length > 0) {
            const [x, y] = queue.shift()!;
            
            for (let k = 0; k < 8; k++) {
                const nx = x + dx[k];
                const ny = y + dy[k];
                if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] === -1) {
                    d[nx][ny] = d[x][y] + 1;
                    queue.push([nx, ny]);
                }
            }
        }
        
        for (let i = 0; i < n; i++) {
            res[i] = d[pawns[i][0]][pawns[i][1]];
        }
        return res;
    };
    
    // Compute distances from initial knight position and each pawn position
    dist[0] = bfs(kx, ky);
    for (let i = 0; i < n; i++) {
        dist[i + 1] = bfs(pawns[i][0], pawns[i][1]);
    }
    
    // Memoization map
    const memo = new Map<string, number>();
    
    const dfs = (pos: number, mask: number, alice: boolean): number => {
        const key = `${pos},${mask},${alice}`;
        
        if (memo.has(key)) {
            return memo.get(key)!;
        }
        
        let best = alice ? -Infinity : Infinity;
        let anyMove = false;
        
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) === 0) continue;
            const d = dist[pos][i];
            if (d < 0) continue;
            anyMove = true;
            const nextVal = dfs(i + 1, mask ^ (1 << i), !alice) + d;
            if (alice) {
                best = Math.max(best, nextVal);
            } else {
                best = Math.min(best, nextVal);
            }
        }
        
        if (!anyMove) {
            memo.set(key, 0);
            return 0;
        }
        
        memo.set(key, best);
        return best;
    };
    
    return dfs(0, (1 << n) - 1, true);
}

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.