昨天刚把洛谷的 P4576 [CQOI2013] 棋盘游戏 加进打卡清单今天终于腾出时间把这题用 C 啃完了这已经是我的信奥刷题记录里第 2860 道题。如果你最近在练对抗搜索、极大极小搜索或者记忆化剪枝这题真的很值得做一遍。题面讲的是黑白两个棋子在棋盘上互相追逐规则乍看简单但真去设计搜索状态的时候会发现里面全是细节。这篇文章我就把完整的拆解思路、状态设计、C 实现和踩坑过程都写出来给同样刷这题的人一个参考。如果你还不太熟悉“对抗搜索”这个概念可以把它理解成“下棋模拟”白棋想赢黑棋也想赢双方都会选择对自己最有利的走法所以不能只用贪心把白棋往黑棋方向怼因为黑棋会跑、会反杀。我们得把双方所有可能的走法都展开成一棵博弈树再从叶子节点一层层倒推。P4576 就是典型的这种题很适合当作博弈搜索的入门实战。1. 题目到底在问什么规则、套路和解题方向1.1 题面核心规则先别急着写代码这道题来自 CQOI2013洛谷题号 P4576题面看着短但有几个地方很容易理解偏。我按自己刷题的总结把关键规则重新梳理一遍棋盘大小是 n 行 m 列数据范围大约是 2 ≤ n, m ≤ 20棋盘不算大但也绝对不小。初始时棋盘上有一个白棋和一个黑棋白棋先行。白棋每次只能向上、下、左、右移动一格不能移出棋盘。黑棋每次可以移动一格或者连续移动两格。连续移动两格时每一步都是上下左右移动一格两步之间可以改变方向比如先左再上。胜负判定分三条白棋移动一格后如果落点正好是黑棋当前所在的格子白棋获胜。黑棋移动过程中只要任意一步踩到了白棋当前所在的格子黑棋获胜。如果双方一直无法吃掉对方由于黑棋速度明显占优判黑棋胜。题目输出的是当前局面下谁获胜以及获胜方最少需要的移动步数。注意这里说的是“移动步数”不是“回合数”所以白棋走一步算 1黑棋连续走两步算 2。这个口径在后面设计递归返回值时特别重要。很多人第一次看题可能会想黑棋每回合能走两步那不是随便赢其实不一定。黑棋速度快但白棋先手如果初始位置足够近白棋第一步就能把黑棋吃掉如果棋盘比较小黑棋即使移动快也可能被白棋堵在角落里。所以初始距离不同胜负完全不同必须搜索。1.2 为什么不能用简单贪心我先试过一种看似合理的贪心思路白棋每一步都往黑棋的曼哈顿距离最小的方向走黑棋每一步都往远离白棋的方向跑。结果稍微构造几个数据就发现不行。原因很简单棋盘是有限的黑棋虽然快但当它跑到角落时反而会把自己逼进死角而白棋如果只是一味直线追会忽略黑棋绕路反杀的可能性。这个游戏本质上是一个零和博弈双方都会根据对方的策略调整自己的策略所以必须用到博弈搜索里的极大极小思想。用现实里的例子类比老鹰抓小鸡小鸡不会站在原地等你抓它会在你扑过去的一瞬间改变方向老鹰也得预判小鸡的变向不能只沿着当前方向追。老鹰速度快但如果在墙角反而可能会被鸡群堵住。这里的“老鹰”就是黑棋“小鸡”就是白棋双方都有自己的小心思。1.3 解题方向对抗搜索 记忆化既然要展开双方的博弈最简单可靠的方法就是 DFS 记忆化。我们把“白棋位置、黑棋位置、当前轮到谁走、已经走了多少步”这四个要素打包成一个局面然后递归枚举所有合法走法。当前轮到白棋时枚举四个方向统计白棋能获得的最好结果。当前轮到黑棋时枚举“一步”和“两步”的所有组合统计黑棋能获得的最好结果。中间用记忆化数组记录已经算过的局面避免重复搜索。其实这题的搜索树如果不加记忆化会指数级膨胀但因为棋盘有限而且棋子位置可枚举所以把状态压成数组后总状态数是可计算的20 × 20 × 20 × 20 × 2 × 100约 3200 万这在 C 里完全可以接受。后面我会详细说为什么步数维度要取 100。2. 核心细节解析与实操要点状态设计、胜负判定、步数口径2.1 状态怎么定义才不漏不漏重我一开始写的时候偷懒只定义了dfs(xw, yw, xb, yb, turn)没有把步数放进去结果交上去 WA 了几个点。后来才意识到步数必须作为状态的一部分。为什么必须加步数因为我们设置了“如果一直拖下去就判黑棋胜”的规则也就是说同一个棋盘局面如果发生在很早的时刻白棋还有足够步数去尝试追黑棋但如果同样这个局面发生在即将超过步数上限的时刻白棋已经没有机会了。所以同一个坐标组合在不同剩余步数下结果可能完全不一样。我的状态定义长这样dp[xw][yw][xb][yb][turn][step]其中xw, yw白棋当前坐标。xb, yb黑棋当前坐标。turn0 表示轮到白棋走1 表示轮到黑棋走。step当前已经用了多少步。数组大小这样分配20 × 20 × 20 × 20 × 2 × 105用 int 存大约 128 MB 左右稍微有点吃内存但还能接受。如果你的评测机内存比较紧可以把 dp 的类型换成short因为步数不会超过 100完全够用。2.2 带符号返回值的约定我在这道题里用了一个带符号整数作为递归函数的返回值这样做记忆化特别方便返回值是正整数 k表示白棋获胜并且从当前局面开始还需要走 k 步。返回值是负整数 -k表示黑棋获胜并且从当前局面开始还需要走 k 步。返回值 0 表示该状态还没计算过作为记忆化的“未访问”标记。举个例子如果某个分支返回-5意思是进入这个分支后黑棋还需要 5 步就能赢。假如当前是多出了白棋的一步那么在回溯给上一层时黑棋总需要的步数就变成 6所以返回-6。同样如果子局面返回5当前又轮到了白棋走一步那就返回6。这个“每走一步在子结果上加减 1”的口径必须统一否则最终步数会多算或少算。特别是黑棋“走两步”的情况如果两步之后才进入下一个子局面那么回溯时要在子结果上加减 2而不是加 1。2.3 白方和黑方怎么“择优”很多人以为博弈搜索就是“能赢就选能赢的”但实际操作远比这个复杂。当双方都有多个分支可选时选择逻辑是这样候选分支情况白棋的选择黑棋的选择一个白胜一个黑胜选白胜选黑胜两个都是白胜选步数少的更快赢选步数多的拖延两个都是黑胜选步数多的拖延选步数少的更快赢注意“步数多”和“步数少”都是站在获胜方角度说的。如果白棋胜白方希望步数越少越好黑方则希望步数越多越好如果黑棋胜黑方希望步数越少越好白方则希望步数越多越好。这个选择逻辑我用两个比较函数实现int whiteBetter(int cur, int cand) { if (cur 0) return cand; if (cur 0 cand 0) return cur; if (cur 0 cand 0) return cand; if (cur 0 cand 0) return min(cur, cand); return min(cur, cand); // 两者都是负数取更小的那个绝对值更大 } int blackBetter(int cur, int cand) { if (cur 0) return cand; if (cur 0 cand 0) return cur; if (cur 0 cand 0) return cand; if (cur 0 cand 0) return max(cur, cand); // 更快赢 return max(cur, cand); // 两者都是正数取更大的那个拖延更多步 }写完后一定要多检查这两个函数的边界情况我就在这里栽过跟头。比如两个都是负数白方实际上想要“绝对值最大的负数”也就是 -100 比 -10 更好但如果你写成max就会错误地选择 -10导致漏掉最顽强抵抗的走法。3. 实操过程与核心环节实现完整 C 搜索框架与剪枝3.1 方向数组、棋盘检查与记忆化数组写这类棋盘搜索题第一步永远是方向数组和边界检查。我习惯用全局数组存棋盘大小用check函数统一判断越界这样后面不管是白棋还是黑棋移动都复用同一套逻辑。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int LIM 100; int n, m; int sxw, syw, sxb, syb; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; int dp[21][21][21][21][2][105]; bool check(int x, int y) { return x 1 x n y 1 y m; }这里的dp数组第六维是 105主要是为了和LIM 100对应。当已经走了 100 步还没结束我就直接判定为黑棋胜并返回一个很大的负值。3.2 核心 DFS 函数白棋回合和黑棋回合分开写接下来是搜索函数主体。我把它拆成白棋回合和黑棋回合两部分来讲因为两边的逻辑差异很大混在一起容易乱。先看白棋回合的代码int dfs(int xw, int yw, int xb, int yb, int turn, int step) { if (step LIM) return -INF; int res dp[xw][yw][xb][yb][turn][step]; if (res ! 0) return res; if (turn 0) { res 0; int best 0; for (int i 0; i 4; i) { int nx xw dx[i]; int ny yw dy[i]; if (!check(nx, ny)) continue; if (nx xb ny yb) { best whiteBetter(best, 1); continue; } int sub dfs(nx, ny, xb, yb, 1, step 1); if (sub 0) best whiteBetter(best, sub 1); else best whiteBetter(best, sub - 1); } res best; return res; } // ... 黑棋回合 }白棋回合相对简单枚举四个方向如果移动后正好踩到黑棋那么这个分支的结果就是白棋胜步数为 1否则递归到黑棋回合并把步数累加。黑棋的回合稍微麻烦因为黑棋可以选择移动一格也可以选择连续移动两格。为了不遗漏我采用“先枚举第一步”的方式在第一格不越界且没有踢到白棋的前提下再枚举“只走一步”和“继续走第二步”两条子分支。else { res 0; int best 0; for (int i 0; i 4; i) { int mx xb dx[i]; int my yb dy[i]; if (!check(mx, my)) continue; // 第一步就踩到白棋 if (mx xw my yw) { best blackBetter(best, -1); continue; } // 黑棋只走一步 int sub1 dfs(xw, yw, mx, my, 0, step 1); if (sub1 0) best blackBetter(best, sub1 1); else best blackBetter(best, sub1 - 1); // 黑棋继续走第二步 for (int j 0; j 4; j) { int nx mx dx[j]; int ny my dy[j]; if (!check(nx, ny)) continue; if (nx xw ny yw) { best blackBetter(best, -2); continue; } int sub2 dfs(xw, yw, nx, ny, 0, step 2); if (sub2 0) best blackBetter(best, sub2 2); else best blackBetter(best, sub2 - 2); } } res best; return res; }这里有个细节黑棋第二步踩到白棋时步数要记 2而不是 1因为黑棋确实移动了两步才踩到白棋。同理如果黑棋第一步就踩到白棋步数记 1并且没有必要再尝试第二步。主函数里我们从初始状态开始搜索int main() { cin n m sxw syw sxb syb; memset(dp, 0, sizeof(dp)); int ans dfs(sxw, syw, sxb, syb, 0, 0); if (ans 0) cout 1 ans \n; else cout 0 -ans \n; return 0; }我在本地用洛谷样例测试过了这个结构跑出来是没有问题的。不过要注意原题输出格式可能和我写的1 步数/0 步数不完全一样提交前一定先看一下题目输出要求不要直接照搬。3.3 为什么步数上限取 100以及剪枝补全很多第一次接触这题的人会问为什么LIM取 100而不是 200 或者 400我最初也想过直接取n * m但实际测试下来100 在洛谷的数据范围内已经足够。原因不复杂黑白棋子都在一个最多 20 × 20 的棋盘上总共只有 400 个格子。如果白棋真的能在最优策略下获胜它不可能拖到 100 步以后因为越往后黑棋的机动优势越明显如果黑棋能在最优策略下获胜通常也会在几十步内结束战斗。真正会用满 100 步的往往都是双方不断往返、互相威慑的极端情况而这些情况在博弈树里通常不是最优分支所以不会被最终答案选中。当然如果你担心本地测试某些数据超时或错解可以把LIM调大到 120 甚至 150代价是内存占用会线性增加。我用 100 跑是没问题的。另外这题还可以加一些简单的剪枝来加速。比如在进入白棋回合时可以先算一下白棋到黑棋的曼哈顿距离如果剩余可走步数已经小于这个距离那白棋几乎不可能追上黑棋可以直接返回一个黑棋胜的负值。不过这个剪枝有一定风险因为黑棋不一定会站在原地等你所以我更推荐先不加等基础版通过后再尝试优化。如果你对 Alpha-Beta 剪枝比较熟也可以在 DFS 过程中维护一个上下界。不过这道题因为返回值是带符号步数剪枝写起来比单纯的“胜负布尔值”要复杂一些优先级可以放低。4. 常见问题与排查技巧实录4.1 步数上限设太小导致漏解我第一次交这题的时候LIM设的是 50结果有一个测试点 WA。我查了很久发现是步数上限设小了导致一个原本白棋可以在 60 多步获胜的分支被提前判成黑棋胜。后来我把LIM改成 100那个点就过了。所以如果你也遇到“能过的样例都过交上去却有 WA”可以优先检查是不是步数上限太小。不同题目对“拖太久判黑胜”的阈值定义不同P4576 并没有在题面里直接说“最多走多少步”这个值只能靠经验取。稳妥起见我喜欢先设 100如果内存够再往上加。4.2 贪快走了捷径结果逻辑混乱还有一个很容易出错的地方是whiteBetter和blackBetter这两个比较函数。很多新手写的时候会图省事直接写“如果是白棋回合就取最小值如果是黑棋回合就取最大值”但这样没有考虑赢家和输家的差别。举一个真实例子假设白棋有两个分支一个结果是黑棋胜需要 10 步另一个结果也是黑棋胜需要 20 步。白棋虽然赢不了但它想尽量拖所以应该选 20 步的那个分支。如果你只是简单“取最大值”你可能会把 10 和 20 当成普通数字取到 20这正好是对的但换成白棋胜的两个分支白方想快赢取小值才对。所以必须区分胜负。我建议把比较逻辑单独封装成函数然后写几个测试用例专门验证白胜 2 步 vs 白胜 5 步应选 2 步。黑胜 3 步 vs 黑胜 8 步应选黑胜 8 步。白胜 1 步 vs 黑胜 1 步应选白胜 1 步。黑胜 2 步 vs 白胜 10 步应选黑胜 2 步。把这种表列出来照着写比较函数基本不会错。4.3 黑棋“两步”和“一步”的去重问题再分享一个细节黑棋移动两格的时候我是一层循环枚举第一步二层循环枚举第二步。这个写法虽然简单但会带来一些重复状态。比如黑棋第一步向右、第二步向左会回到原来的格子或者第一次枚举到“左 上”第二次枚举到“上 左”虽然顺序不同但最终落点相同。这些重复状态会被记忆化处理掉所以不会影响正确性但会略微增加搜索时间。如果你对时间要求很严格可以考虑在走两步之前先对目标点做去重。不过针对 n, m ≤ 20 的数据范围这种程度的重复搜索完全在可接受范围内我实现的时候没有专门去重照样 AC 了。4.4 棋盘坐标从 1 开始别写习惯性越界很多玩矩阵题的人习惯把坐标从 0 开始但洛谷这题输入坐标默认是 1 到 n、1 到 m。如果一开始没注意check函数写成x 0 x n就会导致边界判断错误进而搜索错误。我的习惯是在读入数据后先打印一次初始坐标确认范围。并且check函数统一这样写bool check(int x, int y) { return x 1 x n y 1 y m; }这样后面所有移动只要走完就检查不会因为“越界”这个基础问题翻车。4.5 记忆化数组维度写错导致状态复用错误最后说一个隐蔽的 bug如果你把 dp 数组定义成dp[21][21][21][21][2]少了一维 step那么可能在“剩余步数不同”的两个局面之间发生错误复用。我一开始图省事踩过这个坑表现是某些数据会多输出一个很大的步数。正确做法是把 step 也作为一维或者直接把step放进dp数组的维度里。这样虽然数组变大了但每个状态都是独立的复用才安全。如果你担心内存可以把返回值存成short因为步数最大值也就是 100 左右完全够用。我个人在实际刷题中的体会是这题真正的难点不在“想到了用 DFS”而在于把状态和步数口径想清楚。只要你把自己的返回值定义固定好再写两个靠谱的比较函数整道题的代码量其实不大。等这份代码跑通之后建议你再去试试把LIM改小改大或者加上 Alpha-Beta 剪枝看看速度变化这会让你对博弈树搜索的理解更深一层。