本文涉及知识点
LeetCode3283. 吃掉所有兵需要的最多移动次数
给你一个 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 <= 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 +动态规划之记忆化搜索 + 博弈
注意：国际象棋没有马腿。
n = pos.length
pos2 = pos， pos追加{kx,ky}
dis[i][j] 记录pos[i]到pos[j]的最少跳跃次数。
动态规划的状态表示
dp[i][m] 记录吃光剩余兵需要的跳跃次数。马在pos2[i],(1<<i)&m表示第i个兵是否存活。为了方便，增加变量bTurn表示当前回合是否是Alice的回合。
dp[i][m] 为-1表示未0处理。
记忆化搜索的函数Rec
函数的参数：i,m,bTurn
如果m等于0，return 0。
如果dp[i][m]不是-1，return dp[i][m]。
如果bTurn ，
枚举存活的兵j
return dp[i][m] = max(dis[i][j] + Rec(j,m ^( 1 << j ),false)
如果是Bom的回合：
return dp[i][m] = min(dis[i][j] + Rec(j,m ^( 1 << j ),true)
初始调用
return Rec(n,(1<<n)-1,true)
代码
核心代码
class Solution {
public:
int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
const int N = positions.size();
const int N2 = N + 1;
vector<pair<int, int>> pos2;
for (const auto& v : positions) {
pos2.emplace_back(v[0], v[1]);
}
pos2.emplace_back(kx,ky);
vector<vector<int>> dis(N2, vector<int>(N2));
for (int i = 0; i < N2; i++) {
auto dis1 = Dis(pos2[i].first, pos2[i].second);
for (int j = 0; j < N2; j++) {
dis[i][j] = dis1[pos2[j].first][pos2[j].second];
}
}
vector<vector<int>> dp(N2, vector<int>(1 << N,-1));
function<int(int, int, bool)> Rec = [&](int pos, int mask, bool bTurn) {
if (0 == mask) { return 0; }
if (-1 != dp[pos][mask]) {
return dp[pos][mask] ;
}
int a[2] = { INT_MAX / 2,INT_MIN / 2 };
for (int i = 0; i < N; i++) {
if (!((1 << i) & mask)) { continue; }
if (bTurn) {
a[bTurn] = max(a[bTurn], Rec(i, mask ^ (1 << i), !bTurn) + dis[pos][i]);
}
else {
a[bTurn] = min(a[bTurn], Rec(i, mask ^ (1 << i), !bTurn) + dis[pos][i]);
}
}
return dp[pos][mask]= a[bTurn];
};
return Rec(N,( 1 << N)-1, true);
}
vector<vector<int>> Dis(int x, int y) {
const int iNotMay = 1'000'000;
vector<vector<int>> dis(50, vector<int>(50, iNotMay));
queue<pair<int, int>> que;
auto Add = [&](int x, int y,int iDis) {
if ((x < 0) || (x >= 50)) { return; }
if ((y < 0) || (y >= 50)) { return; }
if (iNotMay != dis[x][y]) { return; }
dis[x][y] = iDis;
que.emplace(x, y);
};
pair<int,int> moves[] = { {1,1},{1,-1},{-1,1},{-1,-1} };
Add(x, y, 0);
while (que.size()) {
const auto [x, y] = que.front();
que.pop();
for (const auto& [x1, y1] : moves)
{
Add(x + 2*x1, y + y1, dis[x][y] + 1);
Add(x+x1,y+ 2*y1, dis[x][y] + 1);
}
}
return dis;
}
};
单元测试
int kx, ky;
vector<vector<int>> positions;
TEST_METHOD(TestMethod11)
{
kx = 1, ky = 1, positions = { {0,0} };
auto res = Solution().maxMoves(kx, ky, positions);
AssertEx(4, res);
}
TEST_METHOD(TestMethod12)
{
kx = 0, ky = 2, positions = { {1,1},{2,2},{3,3} };
auto res = Solution().maxMoves(kx, ky, positions);
AssertEx(8, res);
}
TEST_METHOD(TestMethod13)
{
kx = 0, ky = 0, positions = { {1,2},{2,4} };
auto res = Solution().maxMoves(kx, ky, positions);
AssertEx(3, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。