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

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

Code

[{"language":"C++","code":"#include <vector>\n#include <queue>\n#include <tuple>\n#include <unordered_map>\nusing namespace std;\nclass Solution {\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {\n        int n = positions.size();\n        vector<pair<int, int>> pawns;\n        for (auto& p : positions) pawns.emplace_back(p[0], p[1]);\n        vector<vector<int>> dist(n+1, vector<int>(n, 0));\n        auto bfs = [&](int sx, int sy) -> vector<int> {\n            vector<vector<int>> d(50, vector<int>(50, -1));\n            queue<pair<int, int>> q;\n            q.emplace(sx, sy);\n            d[sx][sy] = 0;\n            vector<int> res(n);\n            int dx[8] = {-2,-2,-1,-1,1,1,2,2}, dy[8] = {-1,1,-2,2,-2,2,-1,1};\n            while (!q.empty()) {\n                auto [x, y] = q.front(); q.pop();\n                for (int k = 0; k < 8; ++k) {\n                    int nx = x + dx[k], ny = y + dy[k];\n                    if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1) {\n                        d[nx][ny] = d[x][y] + 1;\n                        q.emplace(nx, ny);\n                    }\n                }\n            }\n            for (int i = 0; i < n; ++i) res[i] = d[pawns[i].first][pawns[i].second];\n            return res;\n        };\n        dist[0] = bfs(kx, ky);\n        for (int i = 0; i < n; ++i) dist[i+1] = bfs(pawns[i].first, pawns[i].second);\n        unordered_map<long long, int> memo;\n        function<int(int, int, int, bool)> dfs = [&](int pos, int mask, int turn, bool alice) -> int {\n            long long key = ((long long)pos << 16) | (mask << 1) | alice;\n            if (memo.count(key)) return memo[key];\n            int best = alice ? -1e9 : 1e9;\n            bool any = false;\n            for (int i = 0; i < n; ++i) {\n                if (!(mask & (1 << i))) continue;\n                int d = dist[pos][i];\n                if (d < 0) continue;\n                any = true;\n                int next = dfs(i+1, mask ^ (1 << i), turn+1, !alice) + d;\n                if (alice) best = max(best, next);\n                else best = min(best, next);\n            }\n            if (!any) return 0;\n            return memo[key] = best;\n        };\n        return dfs(0, (1<<n)-1, 0, true);\n    }\n};","lang":"cpp"},{"language":"Go","code":"func maxMoves(kx int, ky int, positions [][]int) int {\n    n := len(positions)\n    pawns := make([][2]int, n)\n    for i, p := range positions {\n        pawns[i] = [2]int{p[0], p[1]}\n    }\n    \n    // Distance matrix: dist[i][j] = distance from position i to pawn j\n    dist := make([][]int, n+1)\n    for i := range dist {\n        dist[i] = make([]int, n)\n    }\n    \n    // BFS to compute minimum knight moves\n    bfs := func(sx, sy int) []int {\n        d := make([][]int, 50)\n

Related Tags