如果你在一个算法群里问“新手学搜索先做哪道题”十有八九会有人甩给你 P1443。这道题的题面一句话就能说完给一个 n×m 的棋盘放一匹马在 (x,y)问它跳到每个格子最少要几步跳不到就输出 -1。但就是这句话足以把搜索算法里最核心的东西全部串一遍——方向数组怎么设计、队列怎么用、为什么第一次访问到就是最短步数、边界怎么判甚至连输出格式都埋了一个坑。我带了几年竞赛新手BFS 入门课基本固定用这道题讲。不是说它难恰恰是因为它足够简单、足够纯粹没有障碍物没有额外状态盘面就是一张图每个格子的出边都是那 8 条马走日。把这道题彻底吃透之后再去看迷宫的 BFS、多起点 BFS、带状态压缩的 BFS甚至到 Dijkstra、01BFS都会顺畅很多。这篇文章不打算泛泛讲 BFS 概念而是把 P1443 从题意拆解、原理证明、代码实现、手动模拟、避坑排查一条龙走一遍适合刚接触搜索的新手也适合想把这题讲明白的同学。1. 题目解读马的遍历到底要你干什么1.1 题意与输入输出细节P1443 的题面非常简洁但越简洁的题越容易忽略细节。棋盘是 n 行 m 列坐标从 1 开始计数马初始在 (x,y)1 ≤ x ≤ n1 ≤ y ≤ m。马走的是国际象棋里的“日”字从当前格子出发横方向移动 1 格、纵方向移动 2 格或者横方向移动 2 格、纵方向移动 1 格跨到目标格子。这个走法一共有 8 个方向棋盘内的目标格子就是下一步能到达的地方。输入只有一行四个整数分别是 n、m、x、y。输出是一张 n 行 m 列的矩阵某个格子如果马能到达输出最少需要的步数如果不能到达输出 -1。看到“最少步数”四个字搜索方向基本就锁定了等权图上的最短路径BFS 是天然的第一选择。这里还有一个容易忽略的输出细节题目要求每个数字占 5 格左对齐。也就是说数值后面要用空格补齐到 5 个字符宽度。这个要求直接决定了最终输出用什么方式很多第一次交这题的人算法写对了却因为输出格式不对被卡甚至反复 WA 都找不出原因。1.2 从题目拆出三个考点这道题的考点可以拆成三层建模、算法、实现。第一层是建模。把棋盘当成一张无权无向图每个格子是一个节点马能跳到的 8 个位置是它的出边边只在棋盘内部存在。这样“马到某个格子的最少步数”就变成了“图上从起点到每个节点的最短路径长度”。第二层是算法。图上所有边权都为 1每走一步代价是 1最短路可以直接用 BFS。BFS 按层扩展天然保证第一次到达某个节点时的层数就是最短距离这个结论我在后面会专门证明。第三层是实现。搜索代码的骨架非常固定方向数组 队列 访问标记 边界判断。但每一环都有坑8 个方向写漏、队列忘了 pop、数组初始化为 -1 后忘了单独给起点赋值、坐标从 1 开始却按 0 开始做边界判断等等。这三层正是这类题目拿满分需要的全部能力。1.3 为什么不用 DFS也不用 Dijkstra很多新手遇到最短路径第一反应是 DFS。DFS 也能找最短路但方式非常笨它要枚举从起点到目标点的每一条路径在所有路径里取最小。棋盘一放大路径数量是指数增长的5×5 还没什么感觉到 20×20、50×50 就会直接卡死。而且 DFS 是深度优先第一次找到的目标路径未必最短必须把所有路径都走出来才能下结论。Dijkstra 是另一个方向但它解决的是带权图的最短路问题实现复杂度比 BFS 高。本题所有边权都等于 1属于最特殊的情况用 Dijkstra 属于杀鸡用牛刀堆优化的优先级队列反而把简单问题复杂化。BFS 正是“边权全为 1”场景下的最优解——用队列就能保证扩展顺序按层递进不需要任何优先级策略。2. BFS 为什么能保证最先到达的就是最短距离2.1 水波扩散模型我带新手入门时喜欢把 BFS 讲成水面上的水波。起点就是石头落入水面那个点波纹以相同的速度一圈一圈向外扩散。第 0 圈只有起点自己第 1 圈是起点一步能到的格子第 2 圈是这些格子再走一步能到的新格子以此类推。圈数就是步数第 k 圈被覆盖到的格子最短步数就是 k。这个模型最大的好处是直观你绝不会认为最外圈的波纹有可能比内圈更早到达某个点因为扩散是同时同速的。代码里队列就是波前每次从队头取出一个点把它周围还没被“水”碰到的点加到队尾先进先出的顺序保证先入队的层数一定不大于后入队的层数。2.2 等权图上正确性的一句话证明严格说BFS 能求最短路径依赖于一个性质在边权全为 1 的图上第一次访问到某个点时的路径一定是最短的。想证明也不难用反证法。假设某个格子 v 第一次被访问时走了 d 步但真实最短距离是 d并且 d d。那么沿着这条长度为 d 的最短路径走过去v 的前一个节点 w 一定是在第 d-1 层被访问的。BFS 处理第 d-1 层的节点时会把它们的所有邻居入队包括 v。也就是说v 会在第 d 步时就被访问到这与“v 第一次被访问是第 d 步而 d 比 d 小”矛盾。说明假设不成立第一次访问的步数必然就是最短距离。这个证明的要害在于“队列按层处理”——每一层的所有点都被完整处理完才会处理下一层。这也是为什么不能把 DFS 的访问顺序拿来当最短距离DFS 不等层它顺着一条路走到黑。2.3 时间与空间复杂度估算BFS 的复杂度非常干净。棋盘上有 n×m 个格子每个格子最多入队一次、出队一次每出队一个格子就检查它的 8 个方向。所以总操作次数大约就是 8×n×m时间复杂度写作 O(n×m)常数 8 对现代评测机来说完全可以忽略。空间上距离数组要占 n×m 个 int队列最坏情况下可能同时容纳 O(n×m) 个元素。题目范围 n, m ≤ 400n×m 最大就是 160000。用一个 405×405 的 int 数组存距离再加一个队列内存开销非常小实测在评测机上毫秒级返回。3. 代码实现从方向数组到 AC 提交3.1 八个方向怎么写最不容易错马的 8 个走法看起来多用两个数组就可以一次性收纳。方向向量分别是 (1,2)、(2,1)、(2,-1)、(1,-2)、(-1,-2)、(-2,-1)、(-2,1)、(-1,2)把它们拆成 x 方向和 y 方向的两组偏移量int dx[8] {1, 2, 2, 1, -1, -2, -2, -1}; int dy[8] {2, 1, -1, -2, -2, -1, 1, 2};这里要注意dx[i] 和 dy[i] 是配套使用的不能单独看。我见过有人把两个数组顺序写反导致马变成了“飞象”半天查不出问题。写的时候可以按“先横 1 纵 2再横 2 纵 1”的口诀顺一遍就不容易漏方向。对比用 8 个 if 或者 switch 来写数组方式最大的优势是扩展时只需要一个循环代码短、逻辑集中。以后做带障碍的 BFS、多方向搜索也都是同一个套路——先定义偏移量再写一轮 for 循环。3.2 队列与判重BFS 的两根支柱BFS 的队列负责维护“下一步该处理谁”。要用先进先出的容器C 里直接用 STL 的 queue 就够了。每个队列元素是一个坐标可以用结构体封装也可以用 pairint,int我习惯写结构体因为后面想加点信息比如某些状态题需要记录方向时扩展起来方便。判重要解决的是“同一个格子千万不要重复入队”的问题。马从 A 能跳到 B从 C 也能跳到 B如果不做任何标记B 会被入队两次后续还要重复扩展时间和空间都浪费更严重的是某些图上会出现反复互相到达的循环队列永远不会清空。本题可以使用距离数组兼任标记数组初始化所有距离为 -1-1 就表示“还没被访问过”。在扩展时一个很重要的细节是“发现即标记”计算出新坐标之后立刻把距离写进去、立刻入队而不是等出队的时候再标记。发现即标记能从根本上避免重复入队这是 BFS 代码里最值得养成的好习惯。3.3 输出格式题目里暗藏的得分点题目要求每个数字占 5 格、左对齐。C 风格的 printf 一行代码就能搞定printf(%-5d, ans[i][j]);这里的-表示左对齐5表示最小宽度为 5。如果数值不足 5 位右侧补空格如果超过 5 位正常输出完整数值。如果用 C 的 cout需要写成cout left setw(5) ans[i][j];还需要包含 iomanip相比之下 printf 在竞赛里更直观。我见过不少人在这个地方翻车算法写对了数字也对了但忘了左对齐用了右对齐或者想当然在数字后面手动加空格。手动加空格最大的问题是调整宽度时容易出错比如输出-1后面到底补几个空格用%-5d让编译器统一处理才是最稳的。3.4 完整 AC 代码下面是我给新手推荐的标准写法固定数组开大一点省心不容易越界#include bits/stdc.h using namespace std; const int MAXN 405; int n, m, sx, sy; int step[MAXN][MAXN]; int dx[8] {1, 2, 2, 1, -1, -2, -2, -1}; int dy[8] {2, 1, -1, -2, -2, -1, 1, 2}; struct Node { int x, y; }; void bfs() { queueNode q; q.push({sx, sy}); step[sx][sy] 0; while (!q.empty()) { Node cur q.front(); q.pop(); for (int i 0; i 8; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (step[nx][ny] ! -1) continue; step[nx][ny] step[cur.x][cur.y] 1; q.push({nx, ny}); } } } int main() { scanf(%d%d%d%d, n, m, sx, sy); memset(step, -1, sizeof(step)); bfs(); for (int i 1; i n; i) { for (int j 1; j m; j) { printf(%-5d, step[i][j]); } printf(\n); } return 0; }这段代码里起点是在 bfs 函数内部单独赋值为 0 的这一点别漏。如果忘记给起点赋值起点会保持 -1输出第一格就是 -1整个输出全错。队列用 STL 完全没问题虽然 n×m 最大 160000但队列操作十分轻量。如果你追求更极限的常数优化也可以用手写数组模拟队列把队列容量开到 MAXN * MAXNNode q[MAXN * MAXN]; int head 0, tail 0; q[tail] {sx, sy}; while (head tail) { Node cur q[head]; // 扩展逻辑与上面完全一致 }这种写法省去了 STL 封装的一点点开销也方便调试时看整个队列。对于这道题来说不是必须的但我建议新手至少看懂它因为以后写一些卡常严重的搜索题会用到。4. 亲手模拟一遍5x5 棋盘的层扩展实录4.1 第一层从起点开始为了看清 BFS 到底是怎么跑的我用一个 5×5 棋盘、起点 (2,2) 来手工模拟一遍。棋盘行列都从 1 开始所以坐标 (2,2) 是第二行第二列。起点出队扫描它的 8 个方向走 (1,2) 到 (3,4)在棋盘内入队走 (2,1) 到 (4,3)入队走 (2,-1) 到 (4,1)入队走 (1,-2) 到 (3,0)出界跳过走 (-1,-2) 到 (1,0)出界跳过走 (-2,-1) 到 (0,1)出界跳过走 (-2,1) 到 (0,3)出界跳过走 (-1,2) 到 (1,4)入队。所以第一层新增 4 个点(3,4)、(4,3)、(4,1)、(1,4)。这个结果很直观起点在棋盘偏中间的位置离四个边界都不远8 个方向有一半直接出界只剩 4 个合法落点。4.2 第二层与第三层队列是怎么“推开”的处理完第一层的 4 个点之后队列会依次把它们弹出。每个点再扫描自己的 8 个方向遇到已经访问过的起点或者第一层点就跳过遇到合法的新点就标记距离 2 并入队。第二层新增的点一共 10 个(5,5)、(5,3)、(4,2)、(1,3)、(1,5)、(5,1)、(3,1)、(2,4)、(3,5)、(3,3)。为什么不是 4×832 个因为大部分方向要么出界、要么撞回已经访问过的点。这个过程正好体现了 BFS 的筛选逻辑出界判断滤掉棋盘外的位置距离数组的 -1 判断滤掉已经访问过的位置。两个检查条件缺一不可少了出界判断数组越界少了判重队列中会出现大量重复坐标。第三层在第二层的 10 个点基础上继续扩展新增 8 个点(3,2)、(4,5)、(5,4)、(2,1)、(2,3)、(2,5)、(5,2)、(1,2)。到第三层结束时5×5 棋盘一共 25 个格子已经被访问了 1 4 10 8 23 个。剩下两个格子是 (1,1) 和 (4,4)它们会在第四层被访问到。4.3 最终的 5x5 距离表把整个过程整理成距离矩阵如下4 3 2 1 2 3 0 3 2 3 2 3 2 1 2 1 2 1 4 3 2 3 2 3 2这个矩阵从起点 (2,2) 出发第一行第五列的 (1,5) 距离是 2第五行第五列的 (5,5) 距离也是 2而两个相对更偏的格子 (1,1) 和 (4,4) 距离反而是 4。棋盘规模不大但已经能看出马走日的“跨步”特性距离不按曼哈顿距离走而是按跳数走。这也是为什么这类题必须用搜索而不是直接套公式马的走法太跳跃很难归纳出一个简单的数学表达式。手动模拟出这张表之后再用代码跑一遍看到一样的输出你基本就能确定自己的 BFS 写对了。4.4 边界测试1x1 棋盘、贴边起点、不可达格子BFS 写完除了样例最好再自己构造几个边界数据测一下。第一个边界测试是 1×1 棋盘输入1 1 1 1。起点就是终点距离是 0输出应该是占 5 格的一个 0。这个用例专门验证一件事起点坐标等于棋盘唯一格子时不会越界、不会死循环。第二个边界测试是 3×3 棋盘、起点 (1,1)。马从角落出发可以跳到 (2,3) 和 (3,2)但中心的 (2,2) 永远跳不到。运行之后输出的矩阵是0 3 2 3 -1 1 2 1 2这个测试非常有意思它证明了“不是每个格子都一定可达”。马在 3×3 的小棋盘上会漏掉中心点算法会正确地把中心输出为 -1。这也解释了为什么距离数组必须初始化为 -1那些从未被 BFS 碰到的格子保持原样天然就符合题目对不可达点的输出要求。5. 新手实录常踩的坑与排查方法5.1 队列忘了 pop死循环与超时这是我见过次数最多的一个低级错误。新手很容易写出这样的代码Node cur q.front(); // 忘记 q.pop();如果漏掉 pop队头永远是最初的起点。第一次循环把起点的 8 个邻居入队第二次循环还是处理起点邻居们已经被标记过不会再入队但起点也永远不会被移出队列。程序看起来是死循环了评测时表现为超时或者完全跑不出结果。排查方法很简单检查 while 循环里是否每次都执行了q.pop()并且要把q.front()放在pop()之前取出来。如果你想彻底避免这个坑可以试试手写队列用head指针的移动来代替 pop头指针只前进、不回头代码语义更直观。5.2 memset(-1) 的机制与新手的误区很多人第一次看到memset(step, -1, sizeof(step))会困惑memset 不是按字节填充吗为什么填 -1 之后整个 int 数组都是 -1原理是int 类型的 -1 在内存中的每一位都是 1也就是每个字节都是 0xFF。memset 把这个字节值复制到数组的每个字节最终每个 int 的 4 个字节都是 0xFF解释出来恰好就是 -1。所以 memset 填 -1 是安全的数组初始化成任意全 0 或全 1 位模式也都没问题。真正的大坑是memset(step, 1, sizeof(step))新手会以为把所有格子清成 1结果每个 int 变成二进制 00000001000000010000000100000001换算成十进制是 16843009。也就是说memset 只适合把 int 数组初始化成 0 或 -1千万别拿它初始化成其他整数。5.3 1-based 还是 0-based坐标混乱的后果P1443 的棋盘坐标从 1 开始很多人写代码时习惯性地转换成 0-based这本身没有问题但必须整段代码保持一致。最容易出错的是把读入的 n 和 m 搞反。输入格式是 n行数、m列数、x起点行、y起点列如果你下意识认为第一个数是列数后面所有行列判断、输出循环都会对不上答案就会错位。我的建议是代码里从头到尾统一用 1-based 坐标。坐标范围是 1 到 n、1 到 m数组干脆开 405×405判断条件写成nx 1 || nx n不要去跟 0-based 混着写。你只需要在脑子里记住“1 到 n 是合法区间”比来回切换坐标系省心得多。5.4 边界判断写反数组越界历险记边界判断缺了会导致数组越界访问程序可能跑出随机结果也可能直接崩溃。最常见的问题是只判断了部分边界比如只写ny m忘了ny 1一旦马跳到第 0 列数组下标变成负数行为就不可预测了。稳妥的做法是把四个出界条件写全顺序上建议先判断出界再判断是否访问过。因为访问判断要访问step[nx][ny]如果nx或ny本身越界这一步就会访问非法内存。先拦出界再访问数组逻辑上更安全。另外数组开大一点也是好习惯。本题最大 400×400开 405×405 完全够遇到坐标在边缘的情况也不至于真的越界但“开大数组”是兜底不是偷懒的理由边界判断一定要写对。5.5 输出格式不对答案对了照样 WA最后这个坑最冤BFS 写对了答案也对但输出格式不符合题目要求照样 WA。题目说每个数占 5 格、左对齐正确写法是printf(%-5d, step[i][j]);。如果把-丢了变成%5d数字会右对齐格式不对如果写printf(%d , step[i][j]);虽然看起来数字之间有空隔但宽度不对而且行末会多一个空格。虽然很多评测机对行末空格比较宽容但这类“定义不明确”的写法最好别赌。我建议在本地跑样例时把输出重定向到文件里用十六进制编辑器或者cat -A看每一行的末尾确认没有多余字符。这样可以把格式问题一次性暴露出来。6. 把这道题吃透之后几个延伸方向6.1 从 BFS 到一系列最短路算法BFS 能解决的只是边权全为 1 的最短路。如果你把问题升级一下网格中某些格子的通过代价变成 0另外一些变成 1那就是 01BFS用双端队列就能处理。再进一步如果网格中每条边的权值各不相同就不能再用 BFS 了要上 Dijkstra如果图里可能出现负权边那得用 SPFA 或 Bellman-Ford。认真理解 P1443等于把这些算法的地基打了一遍队列按层扩展、第一次访问即最短、访问标记防止重复这些思想在后来的每个最短路算法里都是通用的。区别只是“优先级”由队列这个最简单的容器换成了优先队列、双端队列、或者带松弛操作的迭代过程。6.2 马的遍历的经典变体马的遍历本身有很多变式最出名的是“骑士巡游”——马能否恰好遍历棋盘每个格子一次并回到起点还有“骑士最短路径问题”在带障碍的棋盘上求最少步数也有把棋盘换成三维空间、让马按三维日字跳的题目。这些变式的核心骨架依然是方向数组 队列 判重 边界。变的是方向数组的维度、障碍物标记、或者状态记录方式。所以我才反复强调 P1443 值得精做它不是一道“背代码”的题而是用来建立搜索思维的最小模型。6.3 一点个人体会最后说点带新人的经验。我要求新手做这类题时不查模板手写三遍第一遍对着思路写第二遍合上答案写第三遍换一组随机数据默写。三遍下来方向数组、队列、判重、边界这几个零件基本就长在手上了。踩过几次坑之后我自己的检查流程也固定成了四步先看方向数组对不对再看队列出队入队位置对不对然后看标记在入队前还是入队后最后看输出格式。这套流程对几乎所有 BFS 题都适用写完代码照着过一遍能省下很多次无意义的交题等待。P1443 就是用来练这套流程的最好起点。
