题目描述

给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions，其中 positions[i] = [x_i, y_i] 表示第 i 个兵在棋盘上的位置。

Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：

• 玩家选择一个仍然在棋盘上的兵，然后移动马，通过 最少 的 步数 吃掉这个兵。注意 ，玩家可以选择 任意 一个兵，不一定 要选择从马的位置出发 最少 移动步数的兵。
• 在马吃兵的过程中，马 可能 会经过一些其他兵的位置，但这些兵 不会 被吃掉。只有 选中的兵在这个回合中被吃掉。

Alice 的目标是 最大化 两名玩家的 总 移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。

假设两名玩家都采用 最优 策略，请你返回 Alice 可以达到的 最大 总移动次数。

在一次 移动 中，如下图所示，马有 8 个可以移动到的位置，每个移动位置都是沿着坐标轴的一个方向前进 2 格，然后沿着垂直的方向前进 1 格。

样例

输入：kx = 1, ky = 1, positions = [[0,0]]

输出：4

解释：

马需要移动 4 步吃掉 (0, 0) 处的兵。

输入：kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]

输出：8

解释：

Alice 选择 (2, 2) 处的兵，移动马吃掉它需要 2 步：
    (0, 2) -> (1, 4) -> (2, 2) 。
Bob 选择 (3, 3) 处的兵，移动马吃掉它需要 2 步：
    (2, 2) -> (4, 1) -> (3, 3) 。
Alice 选择 (1, 1) 处的兵，移动马吃掉它需要 4 步：
    (3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1) 。

输入：kx = 0, ky = 0, positions = [[1,2],[2,4]]

输出：3

解释：

Alice 选择 (2, 4) 处的兵，移动马吃掉它需要 2 步：
    (0, 0) -> (1, 2) -> (2, 4)。注意，(1, 2) 处的兵不会被吃掉。
Bob 选择 (1, 2) 处的兵，移动马吃掉它需要 1 步：
    (2, 4) -> (1, 2) 。

限制

• 0 <= kx, ky <= 49
• 1 <= positions.length <= 15
• positions[i].length == 2
• 0 <= positions[i][0], positions[i][1] <= 49
• positions[i] 两两互不相同。
• 输入保证对于所有 0 <= i < positions.length，都有 positions[i] != [kx, ky]。

算法

(宽度优先遍历，状态压缩动态规划) $O(nL^2 + n^2 \cdot 2^n)$

1. 首先通过宽度优先遍历求出任意两个兵位置之间的缩短距离 $d(i, j)$，以及初始位置 $(kx, ky)$ 到所有兵的最短距离 $d(n, i)。
2. 定义状态 $f(mask, i)$ 表示吃掉了二进制状态为 $mask$ 的兵，且最后一次吃的兵为 $i$ 时，当前玩家还能获得的最大/最小总得分。
3. 初始时，$f(2^n - 1, i) = 0$，即所有的兵都被吃掉了，当前玩家还能获得的得分为 0。其余状态待定。
4. 转移时，对于状态 $f(mask, i)$，需要保证 $i$ 在 $mask$ 中，然后枚举一个不在 $mask$ 中的状态 $j$，转移 $f(mask, i) = \max(f(mask, i), f(mask + 2^j, j) + d(i, j))$ 或者 $f(mask, i) = \min(f(mask, i), f(mask + 2^j, j) + d(i, j))$。选择 $max$ 还是 $min$ 取决于当前操作者，也就是状态 $mask$ 中有多少个兵。如果有奇数个，则说明当前操作从 $i$ 到 $j$ 的是 Bob，则取最小值；否则，取最大值。
5. 最终答案为 $\max(f(2^i, i) + d(n, i))$。
6. 注意，此题不能通过正向的动态规划求解，这是因为正向递推没办法确定当前取最大/最小值是否是每个人最优的策略，而逆序的情况则可以得到从当前状态到最终态的最优策略。

时间复杂度

• 预处理的时间复杂度为 $O(nL^2)$，其中 $L$ 为棋盘的长和宽。
• 动态规划的状态数为 $O(n \cdot 2^n)$，转移时间为 $O(n)$。
• 故总时间复杂度为 $O(nL^2 + n^2 \cdot 2^n)$。

空间复杂度

• 需要 $O(L^2 + n \cdot 2^n)$ 的额外空间存储宽度优先遍历的队列，距离数组和动态规划的状态。

C++ 代码

const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

const int N = 15, L = 50;
const int INF = 1000000000;

class Solution {
private:
    int n, w[L][L];
    int f[1 << N][N];

private:
    vector<int> bfs(const vector<int> &s, const vector<vector<int>> &positions) {
        memset(w, -1, sizeof(w));

        queue<int> q;
        w[s[0]][s[1]] = 0;
        q.push(s[0] * L + s[1]);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            int ux = u / L, uy = u % L;
            for (int d = 0; d < 8; d++) {
                int x = ux + dx[d], y = uy + dy[d];
                if (x < 0 || x >= L || y < 0 || y >= L)
                    continue;

                if (w[x][y] == -1) {
                    w[x][y] = w[ux][uy] + 1;
                    q.push(x * L + y);
                }
            }
        }

        vector<int> r(n);
        for (int i = 0; i < n; i++)
            r[i] = w[positions[i][0]][positions[i][1]];

        return r;
    }

public:
    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        n = positions.size();
        vector<vector<int>> d(n + 1, vector<int>(n));

        for (int i = 0; i < n; i++)
            d[i] = bfs(positions[i], positions);

        d[n] = bfs({kx, ky}, positions);

        for (int i = 0; i < n; i++)
            f[(1 << i) - 1][i] = 0;

        for (int mask = (1 << n) - 2; mask >= 0; mask--) {
            int cnt = __builtin_popcount(mask);

            for (int i = 0; i < n; i++) {
                if (!((mask >> i) & 1))
                    continue;

                if (cnt & 1) f[mask][i] = INF;
                else f[mask][i] = 0;

                for (int j = 0; j < n; j++) {
                    if ((mask >> j) & 1)
                        continue;

                    if (cnt & 1)
                        f[mask][i] = min(f[mask][i],
                            f[mask | (1 << j)][j] + d[i][j]);
                    else
                        f[mask][i] = max(f[mask][i],
                            f[mask | (1 << j)][j] + d[i][j]);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[1 << i][i] + d[n][i]);

        return ans;
    }
};