当前位置：首页 > news >正文

Kimi LeetCode 3283. 吃掉所有兵需要的最多移动次数 Rust实现

news 2026/6/19 6:05:04

以下是 LeetCode 3283. 吃掉所有兵需要的最多移动次数的 Rust 实现。

解题思路

这道题是一个组合博弈问题，核心思路分为两步：

1. BFS 预处理最短距离
棋盘大小为 50×50，马的移动有 8 个方向。由于最多只有 15 个兵，我们可以：
- 对每个关键位置（兵的初始位置 + 骑士起始位置）做一次 BFS
- 预处理出从每个关键位置到棋盘上所有格子的最短马步距离
- 时间复杂度：O(N × 50²)，其中 N ≤ 15

2. 状态压缩 DP + 博弈论
- 用 `mask`（位掩码）表示哪些兵已经被吃掉
- `dp[i][mask][turn]` 表示当前在位置 `i`，还剩 `mask` 状态的兵，轮到 `turn` 玩家时的最优结果
- Alice 先手，要最大化总移动次数（`turn = 0` 时用 `max`）
- Bob 后手，要最小化总移动次数（`turn = 1` 时用 `min`）
- 时间复杂度：O(N² × 2^N)

Rust 代码

```rust
use std::collections::VecDeque;

impl Solution {
pub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {
let n = positions.len();
const M: usize = 50;
const DIRS: [(i32, i32); 8] = [
(1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2),
];

// Build position list: [pawn positions..., knight start position]
let mut pos_list = positions;
pos_list.push(vec![kx, ky]);

// Precompute shortest knight distances from each key position to all board cells
let mut dist: Vec<Vec<Vec<i32>>> = vec![vec![vec![-1; M]; M]; n + 1];

for i in 0..=n {
let sx = pos_list[i][0] as usize;
let sy = pos_list[i][1] as usize;

let mut visited = vec![vec![false; M]; M];
let mut q = VecDeque::new();
q.push_back((sx, sy));
visited[sx][sy] = true;
let mut moves = 0;

while !q.is_empty() {
let level_size = q.len();
for _ in 0..level_size {
let (x, y) = q.pop_front().unwrap();
dist[i][x][y] = moves;

for &(dx, dy) in &DIRS {
let nx = x as i32 + dx;
let ny = y as i32 + dy;
if nx >= 0 && nx < M as i32 && ny >= 0 && ny < M as i32 {
let nx = nx as usize;
let ny = ny as usize;
if !visited[nx][ny] {
visited[nx][ny] = true;
q.push_back((nx, ny));
}
}
}
}
moves += 1;
}
}

// dp[i][mask][turn] using memoization
// turn: 0 = Alice (maximizes), 1 = Bob (minimizes)
let mut memo: Vec<Vec<Vec<i32>>> = vec![vec![vec![-1; 2]; 1 << n]; n + 1];

Self::dfs(n, 0, 0, n, &dist, &pos_list, &mut memo)
}

fn dfs(
last: usize,
mask: usize,
turn: usize,
n: usize,
dist: &Vec<Vec<Vec<i32>>>,
pos_list: &Vec<Vec<i32>>,
memo: &mut Vec<Vec<Vec<i32>>>,
) -> i32 {
if mask == (1 << n) - 1 {
return 0;
}

if memo[last][mask][turn] != -1 {
return memo[last][mask][turn];
}

let mut res = if turn == 0 { 0 } else { i32::MAX };

for j in 0..n {
if (mask >> j) & 1 == 1 {
continue; // pawn already eaten
}

let px = pos_list[j][0] as usize;
let py = pos_list[j][1] as usize;
let d = dist[last][px][py];
let next = Self::dfs(j, mask | (1 << j), turn ^ 1, n, dist, pos_list, memo);

if turn == 0 {
res = res.max(d + next);
} else {
res = res.min(d + next);
}
}

memo[last][mask][turn] = res;
res
}
}
```