2025-04-15：吃掉所有兵需要的最多移动次数。用go语言，在一个 50 x 50 的国际象棋棋盘上，有一个骑士和若干个士兵。假设骑士的初始位置用两个整数 kx 和 ky 表示，同时士兵的位置用二维数组 positions 表示，其中 positions[i] = [xi, yi] 表示第 i 个士兵的位置。

Alice 和 Bob 正在进行一场轮流进行的游戏，Alice 先手。每个玩家在其回合中可以选择一个仍存活于棋盘上的士兵，并移动骑士以最少的步数吃掉该士兵。值得注意的是，玩家可以选择棋盘上任意一个士兵，而并非一定要选择距离骑士最近的士兵。

Alice 的目标是最大化双方的总移动次数，而 Bob 则希望最小化这个总移动次数，假设两人都遵循最佳策略进行游戏，请求返回可以实现的最大总移动次数。

骑士的移动方式是沿着坐标轴方向前进 2 格，然后再在垂直方向上前进 1 格，因此每次移动可以到达最多 8 个不同的位置。

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] 。

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

输出：4。

解释：

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

题目来自leetcode3283。

解决思路

1. 预处理每个士兵到棋盘上所有格子的最短步数

• 对于每个士兵的位置(xi, yi)，使用广度优先搜索（BFS）计算该士兵到棋盘上所有其他格子的最短步数。因为骑士的移动是对称的，所以从士兵位置出发计算到其他格子的最短步数，等价于从其他格子到该士兵的最短步数。
• 使用一个三维数组dis，其中dis[i][x][y]表示第i个士兵到格子(x, y)的最短步数。
• 对每个士兵的位置进行BFS，填充dis数组。

2. 动态规划状态设计

• 使用状态压缩表示哪些士兵已经被吃掉。因为有最多15个士兵，可以用一个15位的二进制数mask表示当前剩余的士兵（mask的第i位为1表示第i个士兵未被吃掉）。
• 定义f[mask][i]表示在剩余士兵状态为mask时，当前骑士位于第i个士兵的位置（或初始位置）时，双方在最佳策略下的总移动次数。
• 初始状态是mask = 0（所有士兵被吃掉），此时f[0][i] = 0。
• 目标状态是mask = 1<<n - 1（所有士兵未被吃掉），骑士初始位置是(kx, ky)（即第n个位置，因为positions被扩展为包含初始位置）。

3. 动态规划转移

• 从mask小的状态向mask大的状态转移。
• 对于每个mask，根据当前剩余士兵的数量（bits.OnesCount(mask)）的奇偶性决定是Alice还是Bob的回合：
  • 如果是Alice的回合（奇数次剩余士兵），她希望最大化总移动次数，因此f[mask][i]取所有可能转移中的最大值。
  • 如果是Bob的回合（偶数次剩余士兵），他希望最小化总移动次数，因此f[mask][i]取所有可能转移中的最小值。
• 具体转移：
  • 对于当前mask和位置i，枚举所有未被吃掉的士兵j（即mask & (1<<j) != 0）。
  • 计算从位置i到士兵j的最短步数dis[j][x_i][y_i]，并更新f[mask][i]：
    • f[mask][i] = max/min(f[mask][i], f[mask^(1<<j)][j] + dis[j][x_i][y_i])。

4. 初始条件和结果

• 初始时，positions数组被扩展为包含骑士的初始位置(kx, ky)，作为第n个位置。
• 最终结果是f[1<<n - 1][n]，即所有士兵未被吃掉且骑士在初始位置时的总移动次数。

时间复杂度和空间复杂度

• 预处理dis：
  • 对每个士兵进行BFS，棋盘大小为50x50，每次BFS时间复杂度为O(50^2) = O(2500)。
  • 有n个士兵，总时间复杂度为O(n * 2500) = O(n * 2500)。
• 动态规划：
  • 状态数为O(2^n * (n+1))（mask有2^n种，位置有n+1种）。
  • 每个状态转移需要O(n)时间（枚举所有未被吃掉的士兵）。
  • 总时间复杂度为O(2^n * n^2)。
• 总时间复杂度：
  • O(n * 2500 + 2^n * n^2)。
  • 对于n=15，2^15=32768，n^2=225，因此动态规划部分占主导。
• 空间复杂度：
  • dis数组：O(n * 50 * 50) = O(n * 2500)。
  • f数组：O(2^n * (n+1))。
  • 总空间复杂度为O(n * 2500 + 2^n * n)。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
	"math/bits"
)

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]
}

func main() {
	kx := 1
	ky := 1
	positions := [][]int{{0, 0}}
	results := maxMoves(kx, ky, positions)
	fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from collections import deque

def maxMoves(kx, ky, positions):
    dirs = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
    n = len(positions)
    # 计算每个兵的位置的BFS距离
    dis = []
    for pos in positions:
        px, py = pos
        d = [[-1 for _ in range(50)] for _ in range(50)]
        d[px][py] = 0
        q = deque([(px, py)])
        step = 1
        while q:
            level_size = len(q)
            for _ in range(level_size):
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < 50 and 0 <= ny < 50 and d[nx][ny] == -1:
                        d[nx][ny] = step
                        q.append((nx, ny))
            step += 1
        dis.append(d)
    # 添加骑士的位置到positions末尾
    positions.append([kx, ky])
    u = (1 << n) - 1
    # 初始化动态规划数组
    f = [[0] * (n + 1) for _ in range(1 << n)]
    # 处理每个mask
    for mask in range(1, 1 << n):
        for i in range(n + 1):
            x, y = positions[i]
            remaining = bin(u ^ mask).count('1')
            odd = (remaining % 2) == 1
            if odd:
                current_val = math.inf
            else:
                current_val = 0  # 初始化为0，当odd为False时
            tmp = mask
            while tmp:
                lsb = tmp & -tmp
                j = (lsb).bit_length() - 1
                tmp ^= lsb
                prev_mask = mask ^ (1 << j)
                steps = dis[j][x][y]
                candidate = f[prev_mask][j] + steps
                if odd:
                    if candidate < current_val:
                        current_val = candidate
                else:
                    if candidate > current_val:
                        current_val = candidate
            f[mask][i] = current_val
    return f[u][n]

# 示例测试
kx = 1
ky = 1
positions = [[0, 0]]
print(maxMoves(kx, ky, positions))  # 输出: 0