最近在整理搜索题单的时候又翻到了 P1443 马的遍历说实话这题我当年做的时候挺有阴影的。题面短得像一条朋友圈难度标签写着“普及”可第一次提交照样 WA 得莫名其妙。它的本质就是给定一个 n×m 的棋盘和一个马的起点用“日”字跳法算出马到每个格子的最少步数到不了的格子输出 -1。已经会 BFS 的人看这题会觉得简单但真正自己上手写一遍才会发现里面藏着不少新手期的常见坑。这篇文章我把这题从读题、选算法、写代码到踩坑、扩展完整拆一遍算是给正在刷搜索题的朋友一份能直接“抄作业”的复盘。1. 题目到底在问什么——先别急着写代码1.1 “日”字跳法拆出来的 8 个方向马的走法在中文里叫“走日字”放到坐标里其实就是从当前格 (x, y) 出发横向差 2 格、纵向差 1 格或者横向差 1 格、纵向差 2 格。把符号排列组合一下一个点能跳到的目标点一共有 8 个(x±2, y±1) 四个方向加上 (x±1, y±2) 四个方向。这里有一个新手特别容易想歪的地方题目说它是“马”很多人就直接带入中国象棋里“蹩马腿”的规则结果怎么写都不对。洛谷这题里的马更像国际象棋里的骑士Knight它跳的时候不关心路径上有没有棋子挡路只看目标位置在不在棋盘里。所以不要自己去判断马腿这题没有那个设定。你要是强行加一个蹩腿判断等于把简单题做成另一个题了。1.2 为什么这个“最少步数”逼你选 BFS题目要的是“最少步数”不是“随便一条路径”。棋盘上每次跳跃的代价都是 1没有权重差异这正好踩在 BFS 的最强项上。BFS 从起点开始先把一步能到的格子全部扫一遍再从这些格子出发扫两步能到的格子一层一层往外推。因为队列是先进先出的所以后入队的格子步数一定不小于先入队的格子步数。先碰到某个格子时记录下来的步数就是它的最短步数。DFS 不是不能做但 DFS 想求最短路径往往要把所有可行路径都试一遍才能取最小值棋盘稍微大一点就爆炸。400×400 的棋盘如果跑 DFS 去搜每条跳跃路径指数级的状态会让你直接超时。所以这题从算法选型上讲没有悬念BFS而且是最朴素的 BFS。有人可能会问Dijkstra 不也能求最短路径吗能但没必要。Dijkstra 是处理边权不为定值的通用工具这里所有边的权重都是 1用 BFS 的 O(n×m) 就够搬 Dijkstra 反而是杀鸡用牛刀。2. 算法背后的核心逻辑——为什么 BFS 恰好能找到最短路径2.1 “每一步权重都是 1”到底意味着什么把这题抽象成图来看棋盘里每个格子是一个节点马能从一个格子跳到的 8 个格子就是 8 条边。这是一个无向无权图也就是每条边的长度都是 1。在无权图上从一个点到另一个点的“最短路径”本质上就是“经过边数最少的路径”。BFS 的扩展方式保证了一个关键性质每次从队列头部取出的节点其距离值一定不会大于队列里其他任何节点的距离值。因为所有节点的入队顺序是按距离非递减排列的。当你在扩展第 k 层节点时队列里剩下的节点距离要么是 k要么是 k1绝对不可能突然冒出一个距离 k-1 的节点。这个性质就是 BFS 正确性的根。把这个问题生活化一点想象你在一个迷宫里有台对讲机你喊一嗓子所有隔一堵墙的人都能听见那些听见的人再喊一嗓子隔两堵墙的人也能听见。第一次听到某个人声音的时间就是你们之间的最短距离。BFS 就是这么干的每一“嗓子”就是一层。2.2 距离数组的复用——-1 既是初始值也是访问标记很多人在写 BFS 时会额外开一个vis布尔数组来记录某个格子有没有被访问过然后再单独开一个step数组记录步数。这种写法没错但在这题里完全可以合并成一个二维数组dist。思路是初始化整个棋盘所有格子的dist为 -1表示“未访问”。起点入队时把dist[x][y]设为 0。之后每次从队列取出当前格子枚举 8 个方向如果目标格子的dist还是 -1说明没访问过就把它更新成当前格子的 dist 1并加入队列。这样dist数组同时完成了“记录步数”和“标记是否访问”两件事。这个技巧不只是在 P1443 里好用。以后你做带权图、多源搜索、BFS 求连通块都会遇到这种用“特殊初值”来兼作访问标记的思路。本质上它是在问这个格子的状态是否已经被定义过了如果定义过说明它在更早的层就被访问过现在的访问不可能比它更优直接跳过即可。2.3 为什么八个方向的遍历顺序不影响答案有的题解方向数组写法五花八门有人从顺时针排有人从逆时针排有人把顺序打乱也能过。这不是玄学是因为在 BFS 里方向的遍历顺序只影响“同一层内部的访问顺序”不影响“这个节点在第几层被发现”。只要入队时标记这个动作不变任何方向的排列得到的最短步数矩阵都是同一个因为距离由扩展层数决定不由先后顺序决定。不过方向数组的顺序会影响你调试时的输出轨迹。我个人的习惯是把方向按顺时针排列先 (1,2)再 (2,1)再 (2,-1)……这样出了问题看中间变量更容易脑补出几何位置排错体验会好一些。3. 手写代码——从方向数组到队列闭环3.1 方向数组的两种写法最常用的写法是开两个平行的数组const int dx[8] {1, 2, 2, 1, -1, -2, -2, -1}; const int dy[8] {2, 1, -1, -2, -2, -1, 1, 2};下标 i 从 0 到 7每组 (dx[i], dy[i]) 就是从一个中心点出发的 8 个落点偏移。如果你老是背不住这 8 个方向还有一个更不容易出错的生成方式。在 BFS 之前用双重循环把所有满足条件的方向枚举出来vectorpairint, int dirs; for (int i -2; i 2; i) { for (int j -2; j 2; j) { if (i ! 0 j ! 0 abs(i) abs(j) 3) { dirs.push_back({i, j}); } } }条件abs(i) abs(j) 3其实就是在表达“两格加一格”的日字跳法。这样不管你怎么组合得到的方向集合一定是那 8 个。适合那种一上来手写方向就手滑漏方向的人。用表格把这 8 个方向列出来会更直观序号dxdy含义012下2右1121下1右222-1下1左231-2下2左14-1-2上2左15-2-1上1左26-21上1右27-12上2右1这里我习惯把行号看成“向下增加”所以用“下”“上”来描述。每个人坐标习惯不同关键是数组和边界判断保持一致。3.2 入队即标记还是出队再标记——这是最容易翻车的两行代码我刚学 BFS 时特别喜欢写成“出队时判断 visited”。因为直觉上节点出队的那一刻才叫“真正访问过它”。但这样做会带来一个隐患同一个节点可能在入队前被多个邻居同时发现导致它被重复加入队列多次。虽然队列里重复节点不会让距离算错但它会浪费额外的时间和空间严重的时候能把队列撑爆。标准写法应该是“入队即标记”。在决定把邻居压入队列的瞬间就更新它的 dist 值这样后续任何节点再试图访问它时都会因为 dist ! -1 而跳过。用一句口诀来记入队即见光莫等出队悔。这个细节几乎能出现在每一道 BFS 题里养成习惯之后收益很大。再看一下入队和标记的伪代码流程起点入队起点 dist 0 while 队列非空: cur 队首出队 for 8 个方向: nx, ny cur.x dx[i], cur.y dy[i] 如果 nx, ny 越界: 跳过 如果 dist[nx][ny] ! -1: 跳过 dist[nx][ny] dist[cur.x][cur.y] 1 将 (nx, ny) 入队3.3 边界检查的正确姿势棋盘的行号和列号都是 1 开始输入给的 x、y 也是 1 开始。所以在检查目标点 (nx, ny) 是否合法时条件是if (nx 1 || nx n || ny 1 || ny m) continue;这里最容易犯的错是把数组开成int dp[n][m]然后从 0 开始存输入却给 1 开始的坐标。建议直接把数组多开两格比如 C 里开MAXN 2这么大用 1 到 n、1 到 m 的下标来存。多出来的边缘格子即使被越界检查漏掉也只会落在额外空间里不会访问到非法内存。3.4 完整 C 实现#include bits/stdc.h using namespace std; const int MAXN 405; int dist[MAXN][MAXN]; const int dx[8] {1, 2, 2, 1, -1, -2, -2, -1}; const int dy[8] {2, 1, -1, -2, -2, -1, 1, 2}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, x, y; cin n m x y; memset(dist, -1, sizeof(dist)); queuepairint, int q; dist[x][y] 0; q.push({x, y}); while (!q.empty()) { auto cur q.front(); q.pop(); int cx cur.first, cy cur.second; for (int i 0; i 8; i) { int nx cx dx[i]; int ny cy dy[i]; if (nx 1 || nx n || ny 1 || ny m) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[cx][cy] 1; q.push({nx, ny}); } } for (int i 1; i n; i) { for (int j 1; j m; j) { printf(%-5d, dist[i][j]); } printf(\n); } return 0; }memset把数组初始化为 -1 在这题里是成立的因为 -1 在二进制补码里是全 1memset 按字节填充时每个字节都会变成 0xFF最终 int 就是 -1。如果要把数组全初始化为其他值比如 0就没法用 memset 直接做。3.5 Python 实现对比如果你习惯用 Python 打或者面试时要用 Python 写BFS 的思路完全一样from collections import deque n, m, x, y map(int, input().split()) dist [[-1] * (m 1) for _ in range(n 1)] dx [1, 2, 2, 1, -1, -2, -2, -1] dy [2, 1, -1, -2, -2, -1, 1, 2] q deque() q.append((x, y)) dist[x][y] 0 while q: cx, cy q.popleft() for i in range(8): nx cx dx[i] ny cy dy[i] if nx 1 or nx n or ny 1 or ny m: continue if dist[nx][ny] ! -1: continue dist[nx][ny] dist[cx][cy] 1 q.append((nx, ny)) for i in range(1, n 1): for j in range(1, m 1): print(f{dist[i][j]:5}, end) print()Python 版要注意这里用dist[x][y]存的是 1 基坐标所以列表每行多开一个位置避免下标错位。打印时:5表示左对齐占 5 格效果和 C 的%-5d差不多。4. 实测踩坑记录——我在这个题目上交过的罚时4.1 输出格式的坑到底怎么对齐 5 格这题输出要求每个数字占 5 格。很多人在这里用cout dist[i][j] 输出结果样例看起来一模一样但其实是只加了一个空格宽度不够。正确做法是使用printf(%-5d)或cout setw(5)来强制占位宽度。%-5d是左对齐意思是在数字右边补空格让整个字段占 5 个字符位置。如果你用%5d则是在数字左边补空格。这两种写法在评测时通常都能过但视觉上不同。我在对拍时发现洛谷的样例输出看起来更像是每个数字后面跟着几个空格到固定宽度所以我习惯用%-5d这样输出行尾会带着几个空格。评测系统一般不管行尾空格但如果你自己写脚本对比样例要注意先 strip 再比较。setw(5)默认是右对齐要用left操作符配合才能变成左对齐。C 里如果混用 printf 和 cout建议先关掉同步或者干脆统一用一种不然可能出现输出顺序错乱这种低级问题。4.2 起点坐标与数组下标的偏移输入给的是 (x, y)其中 x 是行号y 是列号都是从 1 开始的。有些人因为平时写题从 0 开始惯了直接把dist[x][y] 0写成了dist[x - 1][y - 1] 0然后再把循环范围写成 0 到 n-1。这样做也能做对但非常容易和边界检查打架。我推荐直接 1 基对齐数组多开一点所有循环从 1 开始脑子里少一次换算就少一个 bug。还有一种情况是有人把 x 当成列、y 当成行这会让整个矩阵转置。如果最后输出矩阵的宽高都和样例不一样先检查一下是不是把行列搞反了。4.3 队列里重复节点的隐患前面说的“入队即标记”不是理论洁癖在这个题上真的会有效率差别。如果你在出队时才标记一个在 400×400 棋盘上的中心点可能被重复入队多次最坏情况队列会膨胀好几倍。虽然不一定会超时但这是坏习惯。我在本地用一个 400×400 的棋盘测过入队即标记的版本几乎瞬间跑完出队才标记的版本明显会多做很多无效遍历。4.4 常见错误速查表症状可能原因修正方向输出全是 -1起点没入队或 dist[x][y] 没初始化为 0检查起点初始化输出行列错乱把 x 当列、y 当行按题目定义使用行和列有几步算多了出队时才标记访问改成入队时标记并更新距离数组越界崩溃数组开小了1 基坐标越界访问多开两格空间输出挤成一团没用%-5d或setw(5)控制占位宽度5. 从 P1443 延伸出去——BFS 不止这一种玩法5.1 多源 BFS把起点从 1 个变成 K 个如果题目改成棋盘上有 K 匹马要求每个格子到最近的一匹马要多远这题的思路只需要改一行把 K 个起点全部入队dist 全部初始化为 0然后跑同一个 BFS。这样几个起点同时向外扩展谁先碰到某个格子谁就是离它最近的那个起点。每层扩展距离自然就是最短距离。这个技巧在很多实际场景里都有用比如多仓库送货最短距离、多根火源燃烧时间、多个传感器覆盖范围。BFS 的多源版本本质上还是同一层 BFS只是把“初始层”从单个点扩展成点集。5.2 从二维棋盘到状态空间 BFSP1443 的状态只有二维坐标 (x, y)状态总数是 n×m。以后你会遇到状态更复杂的 BFS比如八数码、华容道、魔方它们的“棋盘”不再是一个平面网格而是整个局面。这时候节点是一个完整的状态转移是从一个状态到另一个状态去重不能再用二维数组而是用哈希表或状态压缩。但 BFS 的核心三角形没变状态定义是什么状态之间怎么转移怎么判断状态已访问。如果你能从 P1443 里主动提炼出这三个要素那么这些难题对你来说也只是状态维度的升级而不是思路的断裂。5.3 怎么系统地把 BFS 学扎实我的建议是别急着刷难题。先做 P1443 这类基础题然后用同一个模板去套另一种棋盘题比如迷宫最短路径、走迷宫收集钥匙、单词接龙图论版再过渡到状态压缩 BFS。每一道题都刻意问自己三个问题状态是什么转移是什么去重怎么做这套模板在你以后做大量搜索题时都会反复出现。打个比方学 BFS 就像学做饭P1443 就是最基础的炒青菜。你不能只背菜谱而是要通过这道菜学会“什么时候下锅、多大火、什么时候调味”这些通用规律之后换食材、换调味根本逻辑是一样的。棋盘从方格子变成状态树无非是从炒青菜换成炒肉丝锅还是那口锅。最后再多说一个我自己的经验做 BFS 题时方向数组写完后先在纸上把 8 个方向画出来再跑代码看前几层的输出确认方向数组没写歪。这样看似多花几秒钟实际上能省掉你后面无数次对着错误答案猜原因的时间。P1443 这题虽然简单但它把 BFS 的地基打得很扎实值得你多花一下午把它吃透。