3283. 吃掉所有兵需要的最多移动次数

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

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

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

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

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

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

示例 1：

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

**输出：**4

解释：

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

示例 2：

**输入：**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) 。

示例 3：

**输入：**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] 。

bfs + 状压集合dp（记忆化搜索）

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
class Solution {
    public int maxMoves(int kx, int ky, int[][] positions) {
        int n = positions.length;
        // dis[i][x][y]：第i个兵到棋盘位置[x,y]的最短步数
        int dis[][][] = new int[n][50][50];
        int dirs[][] = new int[][]{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        for (int i = 0; i < n; i++) {
            int d[][] = dis[i];
            Deque<int[]> dq = new LinkedList<>();
            int vis[][] = new int[50][50];
            int position[] = positions[i], x = position[0], y = position[1];
            dq.offer(new int[]{x, y});
            for (int step = 0; !dq.isEmpty(); step++) {
                int sz = dq.size();
                for (int j = 0; j < sz; j++) {
                    int p[] = dq.poll();
                    x = p[0]; y = p[1];
                    d[x][y] = step;
                    for (int dir[] : dirs) {
                        int nx = x + dir[0], ny = y + dir[1];
                        if (nx < 0 || ny < 0 || nx >= 50 || ny >= 50) continue;
                        if (vis[nx][ny] == 1) continue;
                        dq.offer(new int[]{nx, ny});
                        vis[nx][ny] = 1;
                    }
                }
            }
        }
        int memo[][] = new int[n+1][1<<n];
        return dfs(-1, 0, positions, kx, ky, dis, memo);
    }
    // i：当前位置 mask：当前已经过位置的集合
    private int dfs(int i, int mask, int positions[][], int kx, int ky, int dis[][][], int memo[][]) {
        if (memo[i+1][mask] != 0) return memo[i+1][mask];
        int n = positions.length;
        int k = Integer.bitCount(mask);
        if (k == n) return 0;
        int x = i == -1 ? kx : positions[i][0];
        int y = i == -1 ? ky : positions[i][1];
        int res = k % 2 == 0 ? 0 : Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if (((mask >> j) & 1) > 0) continue;
            if (k % 2 == 0) res = Math.max(res, dfs(j, mask|(1<<j), positions, kx, ky, dis, memo) + dis[j][x][y]);
            else res = Math.min(res, dfs(j, mask|(1<<j), positions, kx, ky, dis, memo) + dis[j][x][y]);
        }
        return memo[i+1][mask] = res;
    }
}

bfs + 状压集合dp（递推）

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
class Solution {
    public int maxMoves(int kx, int ky, int[][] positions) {
        int n = positions.length;
        // dis[i][x][y]：第i个兵到棋盘位置[x,y]的最短步数
        int dis[][][] = new int[n][50][50];
        int dirs[][] = new int[][]{{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        for (int i = 0; i < n; i++) {
            int d[][] = dis[i];
            Deque<int[]> dq = new LinkedList<>();
            int vis[][] = new int[50][50];
            int position[] = positions[i], x = position[0], y = position[1];
            dq.offer(new int[]{x, y});
            for (int step = 0; !dq.isEmpty(); step++) {
                int sz = dq.size();
                for (int j = 0; j < sz; j++) {
                    int p[] = dq.poll();
                    x = p[0]; y = p[1];
                    d[x][y] = step;
                    for (int dir[] : dirs) {
                        int nx = x + dir[0], ny = y + dir[1];
                        if (nx < 0 || ny < 0 || nx >= 50 || ny >= 50) continue;
                        if (vis[nx][ny] == 1) continue;
                        dq.offer(new int[]{nx, ny});
                        vis[nx][ny] = 1;
                    }
                }
            }
        }
        // f[i][mask]: 当前位已走过位置的集合是mask 并且当前位置是i的状态下的两玩家最优移动次数
        int f[][] = new int[n+1][1<<n];
        for (int mask = (1<<n)-1; mask >= 0; mask--) {
            int k = Integer.bitCount(mask);
            // 这里要注意这里要考虑 k == n 的情况，否则下面可能把f[n][1<<n-1]初始化成无穷大
            if (k == n) continue;  // 也可以省略这句，直接把mask初始化成(1<<n)-2
            for (int i = n-1; i >= -1; i--) {
                int x = i == -1 ? kx : positions[i][0];
                int y = i == -1 ? ky : positions[i][1];
                f[i+1][mask] = k % 2 == 0 ? 0 : Integer.MAX_VALUE;
                for (int j = 0; j < n; j++) {
                    if (((mask >> j) & 1) > 0) continue;
                    if (k % 2 == 0) f[i+1][mask] = Math.max(f[i+1][mask], f[j+1][mask|(1<<j)] + dis[j][x][y]);
                    else f[i+1][mask] = Math.min(f[i+1][mask], f[j+1][mask|(1<<j)] + dis[j][x][y]);
                }
            }
        }
        return f[0][0];
    }
}