LeetCode 题解工作台
吃掉所有兵需要的最多移动次数
给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [x i , y i ] 表示第 i 个兵在棋盘上的位置。 Alice 和 …
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
我们首先预处理出每个兵到棋盘上任意一个位置的马的最短距离，记录在数组 中，即 表示第 个兵到 $(x, y)$ 位置的马的最短距离。 接下来，我们设计一个函数 $\text{dfs}(\textit{last}, \textit{state}, \textit{k})$，其中 表示上一个吃掉的兵的编号，而 表示当前还剩下的兵的状态，而 表示当前是 Alice 还是 Bob 的回合。函数…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个兵在棋盘上的位置。
Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：
- 玩家选择一个仍然在棋盘上的兵，然后移动马，通过 最少 的 步数 吃掉这个兵。注意 ，玩家可以选择 任意 一个兵，不一定 要选择从马的位置出发 最少 移动步数的兵。
- 在马吃兵的过程中，马 可能 会经过一些其他兵的位置，但这些兵 不会 被吃掉。只有 选中的兵在这个回合中被吃掉。
Alice 的目标是 最大化 两名玩家的 总 移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。
假设两名玩家都采用 最优 策略，请你返回可以达到的 最大 总移动次数。
在一次 移动 中，如下图所示，马有 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 <= 491 <= positions.length <= 15positions[i].length == 20 <= positions[i][0], positions[i][1] <= 49positions[i]两两互不相同。- 输入保证对于所有
0 <= i < positions.length，都有positions[i] != [kx, ky]。
解题思路
方法一：BFS + 状态压缩 + 记忆化搜索
我们首先预处理出每个兵到棋盘上任意一个位置的马的最短距离，记录在数组 中，即 表示第 个兵到 位置的马的最短距离。
接下来，我们设计一个函数 ，其中 表示上一个吃掉的兵的编号，而 表示当前还剩下的兵的状态，而 表示当前是 Alice 还是 Bob 的回合。函数的返回值表示当前回合的最大移动次数。那么答案为 。这里我们初始时上一个吃掉的兵的编号记为 ，这也是马所在的位置。
函数 的具体实现如下：
- 如果 ，表示没有兵了，返回 ；
- 如果 ，表示当前是 Alice 的回合，我们需要找到一个兵，使得吃掉这个兵后的移动次数最大，即 ；
- 如果 ，表示当前是 Bob 的回合，我们需要找到一个兵，使得吃掉这个兵后的移动次数最小，即 。
为了避免重复计算，我们使用记忆化搜索，即使用哈希表记录已经计算过的状态。
时间复杂度 ，空间复杂度 。其中 和 分别为兵的数量和棋盘的大小。
class Solution:
def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
@cache
def dfs(last: int, state: int, k: int) -> int:
if state == 0:
return 0
if k:
res = 0
for i, (x, y) in enumerate(positions):
if state >> i & 1:
t = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y]
if res < t:
res = t
return res
else:
res = inf
for i, (x, y) in enumerate(positions):
if state >> i & 1:
t = dfs(i, state ^ (1 << i), k ^ 1) + dist[last][x][y]
if res > t:
res = t
return res
n = len(positions)
m = 50
dist = [[[-1] * m for _ in range(m)] for _ in range(n + 1)]
dx = [1, 1, 2, 2, -1, -1, -2, -2]
dy = [2, -2, 1, -1, 2, -2, 1, -1]
positions.append([kx, ky])
for i, (x, y) in enumerate(positions):
dist[i][x][y] = 0
q = deque([(x, y)])
step = 0
while q:
step += 1
for _ in range(len(q)):
x1, y1 = q.popleft()
for j in range(8):
x2, y2 = x1 + dx[j], y1 + dy[j]
if 0 <= x2 < m and 0 <= y2 < m and dist[i][x2][y2] == -1:
dist[i][x2][y2] = step
q.append((x2, y2))
ans = dfs(n, (1 << n) - 1, 1)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of pawns (up to 15), producing O(2^n * n^2) due to bitmask states and pairwise distance checks. Space complexity is O(2^n * n + board_size^2) for memoization and BFS distance storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem tests combining BFS for knight moves with bitmask dynamic programming.
- question_mark
Expect discussion of array indexing errors and optimizing state transitions.
- question_mark
Watch for understanding how Alice and Bob's optimal strategies affect total move count.
常见陷阱
外企场景- error
Not correctly preprocessing knight moves with BFS, leading to repeated calculations.
- error
Mismanaging bitmask states or forgetting memoization, causing timeouts.
- error
Failing to handle optimal game strategy, giving incorrect maximum total moves.
进阶变体
外企场景- arrow_right_alt
Maximize moves with a bishop or rook instead of a knight, changing movement constraints.
- arrow_right_alt
Use larger chessboards or more pawns to test scalability of bitmask DP approach.
- arrow_right_alt
Minimize total moves instead of maximizing, reversing Alice and Bob strategies.