列表

详情

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

解释：

示例 3：

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

输出：3

解释：

 

提示：

相似题目

骑士在棋盘上的概率

检查骑士巡视方案

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int maxMoves(int kx, int ky, vector<vector<int>>& positions) { } };

golang 解法, 执行用时: 261 ms, 内存消耗: 15 MB, 提交时间: 2024-10-22 09:29:06 

func maxMoves(kx, ky int, positions [][]int) int {
	type pair struct{ x, y int }
	dirs := []pair{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}
	n := len(positions)
	// 计算马到兵的步数，等价于计算兵到其余格子的步数
	dis := make([][50][50]int, n)
	for i, pos := range positions {
		d := &dis[i]
		for j := range d {
			for k := range d[j] {
				d[j][k] = -1
			}
		}
		px, py := pos[0], pos[1]
		d[px][py] = 0
		q := []pair{{px, py}}
		for step := 1; len(q) > 0; step++ {
			tmp := q
			q = nil
			for _, p := range tmp {
				for _, dir := range dirs {
					x, y := p.x+dir.x, p.y+dir.y
					if 0 <= x && x < 50 && 0 <= y && y < 50 && d[x][y] < 0 {
						d[x][y] = step
						q = append(q, pair{x, y})
					}
				}
			}
		}
	}

	positions = append(positions, []int{kx, ky})
	u := 1<<n - 1
	f := make([][]int, 1<<n)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for mask := 1; mask < 1<<n; mask++ {
		for i, p := range positions {
			x, y := p[0], p[1]
			odd := bits.OnesCount(uint(u^mask))%2 > 0
			if odd {
				f[mask][i] = math.MaxInt
			}
			op := func(a, b int) int {
				if odd {
					return min(a, b)
				}
				return max(a, b)
			}
			for s := uint(mask); s > 0; s &= s - 1 {
				j := bits.TrailingZeros(s)
				f[mask][i] = op(f[mask][i], f[mask^1<<j][j]+dis[j][x][y])
			}
		}
	}
	return f[u][n]
}

python3 解法, 执行用时: 9549 ms, 内存消耗: 23 MB, 提交时间: 2024-10-22 09:28:48 

DIRS = ((2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))

class Solution:
    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
        n = len(positions)
        # 计算马到兵的步数，等价于计算兵到其余格子的步数
        dis = [[[-1] * 50 for _ in range(50)] for _ in range(n)]
        for d, (px, py) in zip(dis, positions):
            d[px][py] = 0
            q = [(px, py)]
            step = 1
            while q:
                tmp = q
                q = []
                for p in tmp:
                    for dx, dy in DIRS:
                        x, y = p[0] + dx, p[1] + dy
                        if 0 <= x < 50 and 0 <= y < 50 and d[x][y] < 0:
                            d[x][y] = step
                            q.append((x, y))
                step += 1

        positions.append((kx, ky))
        u = (1 << n) - 1
        f = [[0] * (n + 1) for _ in range(1 << n)]
        for mask in range(1, 1 << n):
            for i, (x, y) in enumerate(positions):
                odd = (u ^ mask).bit_count() % 2
                res = inf if odd else 0
                op = min if odd else max
                for j, d in enumerate(dis):
                    if mask >> j & 1:
                        res = op(res, f[mask ^ (1 << j)][j] + d[x][y])
                f[mask][i] = res
        return f[-1][n]

java 解法, 执行用时: 445 ms, 内存消耗: 47.7 MB, 提交时间: 2024-10-22 09:28:33 

class Solution {
    private static final int[][] DIRS = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};

    public int maxMoves(int kx, int ky, int[][] positions) {
        int n = positions.length;
        // 计算马到兵的步数，等价于计算兵到其余格子的步数
        int[][][] dis = new int[n][50][50];
        for (int i = 0; i < n; i++) {
            int[][] d = dis[i];
            for (int j = 0; j < 50; j++) {
                Arrays.fill(d[j], -1);
            }
            int px = positions[i][0];
            int py = positions[i][1];
            d[px][py] = 0;
            List<int[]> q = List.of(new int[]{px, py});
            for (int step = 1; !q.isEmpty(); step++) {
                List<int[]> tmp = q;
                q = new ArrayList<>();
                for (int[] p : tmp) {
                    for (int[] dir : DIRS) {
                        int x = p[0] + dir[0];
                        int y = p[1] + dir[1];
                        if (0 <= x && x < 50 && 0 <= y && y < 50 && d[x][y] < 0) {
                            d[x][y] = step;
                            q.add(new int[]{x, y});
                        }
                    }
                }
            }
        }

        int u = (1 << n) - 1;
        int[][] f = new int[1 << n][n + 1];
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i <= n; i++) {
                int x = i < n ? positions[i][0] : kx;
                int y = i < n ? positions[i][1] : ky;
                if (Integer.bitCount(u ^ mask) % 2 == 0) { // Alice 操作
                    for (int j = 0; j < n; j++) {
                        if ((mask >> j & 1) > 0) {
                            f[mask][i] = Math.max(f[mask][i], f[mask ^ (1 << j)][j] + dis[j][x][y]);
                        }
                    }
                } else { // Bob 操作
                    f[mask][i] = Integer.MAX_VALUE;
                    for (int j = 0; j < n; j++) {
                        if ((mask >> j & 1) > 0) {
                            f[mask][i] = Math.min(f[mask][i], f[mask ^ (1 << j)][j] + dis[j][x][y]);
                        }
                    }
                }
            }
        }
        return f[u][n];
    }
}

cpp 解法, 执行用时: 802 ms, 内存消耗: 320.6 MB, 提交时间: 2024-10-22 09:28:20 

class Solution {
    static constexpr int dirs[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
public:
    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        int n = positions.size();
        int dis[n][50][50];
        memset(dis, -1, sizeof(dis));
        // 计算马到兵的步数，等价于计算兵到其余格子的步数
        for (int i = 0; i < n; i++) {
            int px = positions[i][0], py = positions[i][1];
            dis[i][px][py] = 0;
            vector<pair<int, int>> q = {{px, py}};
            for (int step = 1; !q.empty(); step++) {
                vector<pair<int, int>> tmp;
                for (auto& [qx, qy] : q) {
                    for (auto& [dx, dy] : dirs) {
                        int x = qx + dx, y = qy + dy;
                        if (0 <= x && x < 50 && 0 <= y && y < 50 && dis[i][x][y] < 0) {
                            dis[i][x][y] = step;
                            tmp.emplace_back(x, y);
                        }
                    }
                }
                q = move(tmp);
            }
        }

        positions.push_back({kx, ky});
        int u = (1 << n) - 1;
        vector<vector<int>> f(1 << n, vector<int>(n + 1));
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i <= n; i++) {
                int x = positions[i][0], y = positions[i][1];
                if (__builtin_parity(u ^ mask) == 0) { // Alice 操作
                    for (int j = 0; j < n; j++) {
                        if (mask >> j & 1) {
                            f[mask][i] = max(f[mask][i], f[mask ^ (1 << j)][j] + dis[j][x][y]);
                        }
                    }
                } else { // Bob 操作
                    f[mask][i] = INT_MAX;
                    for (int j = 0; j < n; j++) {
                        if (mask >> j & 1) {
                            f[mask][i] = min(f[mask][i], f[mask ^ (1 << j)][j] + dis[j][x][y]);
                        }
                    }
                }
            }
        }
        return f[u][n];
    }
};

上一题

© 2024 leetcode.cn