1. BISHI80走迷宫为什么是这道题如果你刷过算法题或者参与过信息学竞赛的基础训练大概率碰过这类问题给定一个由字符组成的迷宫矩阵起点在左上角终点在右下角#代表墙壁.代表空地要求算出从起点到终点的最短步数或者输出一条可行路径。BISHI80就是这类题中的一个典型代表题目本身不复杂但很多人第一次做的时候会发现思路都懂代码一写一堆bug要么死循环要么答案是错的。我当年带过不少刚开始接触搜索算法的新手发现他们卡住的点非常集中不是不理解BFS的层序扩展而是不知道代码层面怎么把四个方向这个动作写得干净利落。这时候方向数组就派上用场了。它不是一个算法而是一种编码技巧用两个一维数组配合循环把上、下、左、右四个方向的尝试操作从四段重复代码压缩成一段通用逻辑。理解了这个技巧BFS的代码量能减少一半以上而且几乎不会出现方向漏写的问题。这篇文章不打算只贴一份AC代码然后让大家自己看我想把这道题从头到尾拆开从解题思路的选型到方向数组的四种写法对比再到完整代码的逐段解析最后是调试经验和你可能在评测系统里遇到的坑。无论你是刚接触广度优先搜索的初学者还是想把这题讲给学生听的带练者这篇内容应该都能给到你想要的参考。我尽量把代码和讲解都写完整你照着敲一遍比干看十遍都管用。2. 解题思路为什么这题非BFS不可2.1 最短路径问题和层层扩散的直觉迷宫问题的本质是图上的最短路径搜索只不过这个图的节点就是网格中的每一个坐标点边就是相邻空地之间的移动关系。处理最短路径BFS天然是首选因为BFS的扩展顺序是按层来推进的先把起点周围距离为1的所有节点全部入队再处理距离为2的节点依次类推。这意味着当某个节点第一次被访问到时它在队列中的层号就是从起点到它的最短距离。我们用生活场景来类比你在一栋楼里丢了一个包裹公司组织大家一起找。BFS的做法是所有人先从会议室出发把同楼层的每个房间都看一眼然后统一去下一层看而不是一个人先跑到十楼另一个人又扎进地下室。这样能保证最先找到包裹的人走过的路线一定是最短的。DFS则不同它更像一个执着的人顺着一条走廊走到黑走到死胡同再折回来。在只要可达的迷宫问题里DFS够用但在求最短步数的场景下DFS必须要枚举所有路径才能知道哪条最短效率低很多。回到BISHI80这道题题目明确要求输出从起点到终点的最少步数所以方向几乎唯一就是BFS。理解了BFS的层序扩散原理你把队列想象成一个水波扩散的起源点每一圈波纹对应一层步数扩散到终点的那一刻当前步数就是答案。2.2 BFS的三个核心要素写BFS代码之前你需要确定三件事用什么数据结构存待扩展的点、用什么结构记录已访问状态、用什么方式处理边界条件。待扩展的点集合首选队列。一开始只有起点在队列中然后循环执行取出队头节点尝试四个方向的操作把符合条件的邻居节点追加到队尾。这段逻辑里队列天然地维持了先进先出的顺序这正是BFS层序扩展的代码层保证。如果你手头只有数组也可以把它当成循环队列模拟使用不过在笔试题里直接用库里的队列最省事。已访问状态的处理是很多初学者容易忽略的。BFS有一个重要原则一个节点一旦被放入队列就应该立刻标记为已访问而不是等它出队时再标记。为什么我们用一个简单例子说明起点S出队时它的下边和右边两个邻居节点都被加入队列如果这两个邻居节点在后续扩展中都能走到同一个公共节点X而X的已访问标记只有出队时才打上那么X就可能被重复入队两次产生大量冗余计算极端情况下还会导致队列膨胀。正确的做法是在节点入队时立即标记保证每个节点只进入队列一次。这道题体重低于100矩阵规模也不大重复入队可能不会让你超时但养成好习惯总没错。边界条件的处理相对直观无非是检查下一个坐标是否超出矩阵范围以及该位置是否是墙壁。把这些检查统一封装进一个判断逻辑里代码的可读性会高很多。2.3 DFS方案为什么在这个问题里失宠这里我想多说两句DFS。不少人最初学搜索时先接触DFS递归回溯那一套玩得挺溜于是看到迷宫题也下意识写DFS。如果题目只要求判断是否存在路径DFS完全能胜任。但一旦要求最短步数DFS就力不从心了因为它本质上是暴力枚举。你走完一条路径后才能确认它的长度只有把所有可行路径都遍历完才能比较出最短的那条这在最坏情况下是指数级的复杂度。反观BFS因为它按层扩展的特性第一次扩展到终点时的步数一定是最短步数中间不需要比较、不需要回溯逻辑极其简洁。从这个角度说BISHI80选择BFS不是因为它更高级而是在时间复杂度和代码复杂度上都更合理。理解这一点比刷十道类似的题都重要。3. 方向数组代码里的通用方向引擎3.1 方向数组的基本形态方向数组解决的核心问题是把向四个方向移动这样一个空间动作翻译成计算机可以循环执行的整数操作。以常见的二维网格坐标系为例x通常代表行号y代表列号。四个方向的偏移量分别是上-1, 0、下1, 0、左0, -1、右0, 1。代码里最常见的写法是int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};这里的dx和dy是配套使用的。dx[i]和dy[i]一起决定了第i个方向的横纵偏移量。当i0时偏移是(-1, 0)表示向上i1时是(1, 0)表示向下。遍历所有方向时只需要一个for循环for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查 (nx, ny) 是否合法 }我之前见过有人用两个二维数组存方向比如dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}然后通过nx x dir[i][0]来访问这样也可以只是可读性稍微差一点。双一维数组的写法在视觉上更直观而且你不需要额外记忆下标0是x偏移还是y偏移这种细节。需要注意的一点是方向数组的顺序会影响代码的搜索结果。如果你的题目只求最短步数顺序影响不大因为BFS的层序扩展特性保证了首次到达终点的步数一定最短与方向顺序无关。但如果题目要求输出路径方向数组的顺序就会决定你最终找到的路径是哪一条。比如按上、右、下、左的顺序扩展走出来的路线会偏向上方右侧按下、左、上、右则偏爱向下延伸。绝大多数评测系统只校验路径的合法性不校验唯一性但如果你做可视化展示可能需要调一下顺序让路径更好看。3.2 为什么用方向数组而不是四段if初学者最容易写的代码是这样// 向上 if (x - 1 0 grid[x-1][y] .) { q.push({x-1, y}); } // 向下 if (x 1 n grid[x1][y] .) { q.push({x1, y}); } // 向左 if (y - 1 0 grid[x][y-1] .) { q.push({x, y-1}); } // 向右 if (y 1 m grid[x][y1] .) { q.push({x, y1}); }这段代码在小规模迷宫上确实能跑通但问题很明显四个方向的逻辑大量重复一旦你需要修改判断条件得同时改四遍漏一处就出bug。更糟的是如果迷宫允许斜向移动比如八个方向这段代码会膨胀到八段重复逻辑维护难度直线上升。方向数组的核心价值就是把尝试从当前点出发走遍所有相邻方向这个动作抽象成一个循环。你只需要改变方向数组的长度和内容就能轻松适配四方向、八方向甚至马走日这类非规则的移动规则。代码量基本不变。另外方向数组还有一个隐性的好处它天然地避免了方向漏写的问题。只要你的方向数组长度和循环次数一致四个方向一个都跑不了。这对于考试时快速写题、减少低级错误来说价值非常大。3.3 方向数组的排布习惯与技巧我见过不少有经验的竞赛选手会刻意把方向数组按照顺时针或逆时针顺序排列这是有实际意义的。以四方向为例顺时针顺序是上-1,0、右0,1、下1,0、左0,-1。这样排布时dx和dy分别为int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};这样做的好处是在某些需要输出路径、或者在网格上做螺旋遍历的场景下方向的自然顺序会让逻辑更清晰。还有一个实用的技巧如果你需要在代码中临时改变移动优先级比如希望搜索优先向右走只需要调整数组元素的顺序不需要改循环逻辑。对于八方向的问题方向数组会变成八个元素同样可以按顺时针排布上、右上、右、右下、下、左下、左、左上。我个人的建议是把方向数组的排布当成一种约定俗成的书写习惯固定下来这样每次写搜索都不会因为临时想方向顺序是什么而打断思路。4. BISHI80完整实现从读入到答案逐段拆解4.1 数据结构的选取和初始化题目用的是字符矩阵每个位置要么是空地要么是墙壁。我习惯用vectorstring来存迷宫因为每行字符串可以整体读入访问某一行某一列的元素就用grid[x][y]。记录步数的方式有两种。第一种是额外开一个二维数组dist初始化成-1表示未访问然后每进入一个新节点就用前一个节点的步数加一。第二种是把步数直接封装在队列元素里比如队列元素是一个结构体包含x、y、step三个字段。两种方式各有优劣dist数组在调试时可以直接观察每个位置的最短步数但多占用一份内存结构体方式代码简洁不需要额外的数组。对于BISHI80这种小规模迷宫两种方式差别不大我倾向于用dist数组因为后续如果要做可视化、或者想观察BFS扩散过程它更方便。还有一个细节是起点的坐标。题目中起点通常在左上角也就是(0,0)终点在右下角(n-1,m-1)。但保险起见代码里我会做一次检查如果起点就是终点直接输出0避免边界情况的处理出现遗漏。4.2 BFS主循环完整代码直接给出一份可运行的C代码这道题的输入格式通常是第一行两个整数n和m表示迷宫的行数和列数接下来n行是迷宫地图字符包括.空地、#墙壁、S起点和E终点。不同的题目起点终点符号可能不一样但逻辑是通用的。#include bits/stdc.h using namespace std; const int MAXN 100; int n, m; string grid[MAXN]; int dist[MAXN][MAXN]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; bool valid(int x, int y) { return x 0 x n y 0 y m grid[x][y] ! # dist[x][y] -1; } int main() { cin n m; int sx 0, sy 0, ex n - 1, ey m - 1; for (int i 0; i n; i) cin grid[i]; memset(dist, -1, sizeof(dist)); queuepairint, int q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x ex y ey) break; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (valid(nx, ny)) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } cout dist[ex][ey] endl; return 0; }valid函数是这道题的灵魂之一它把越界检查、墙壁检查和访问状态检查全部收拢在一起。初学的时候不要觉得这个函数多余把判断逻辑独立出来后主循环里只剩三行操作基本不会看错。BFS主循环里取出队头节点后立刻判断是否是终点如果是就跳出循环这算是一个微小的优化。因为BFS的特性此时dist[ex][ey]已经是终点的最短步数不需要等待整个队列清空。注意queuepairint, int的使用需要C11标准在代码里手动把{x, y}推入队列是C11的初始化列表写法。如果你用的编译器较老改成q.push(make_pair(x, y))也行。4.3 路径记录扩展从步数到路径输出很多走迷宫题不满足于只输出步数还要输出路径本身。这时候BFS的代码需要做一些增强。核心思路是额外开一个parent数组记录每个节点的前驱节点坐标。当BFS首次访问某个节点时把它是从哪个方向走来的这个信息保存下来。等BFS结束我们从终点逆着parent数组一路回溯到起点得到的就是最短路径的倒序再reverse一下就是正序路径。方向数组在这个环节再次发挥作用。我们需要一个dirs数组它不仅记录偏移量还记录方向的字符标识比如U、D、L、R。结构体写法struct Direction { int dx, dy; char ch; } dirs[4] {{-1,0,U}, {1,0,D}, {0,-1,L}, {0,1,R}};在这个结构体数组里方向和输出字符是一一对应的。遍历方向时我们不仅更新坐标还记录dirs[i].ch。如果你用多个独立数组比如dx[]、dy[]和pathChar[]它们的下标对齐关系很容易在代码维护时被打破。结构体方案把这些信息绑定在一起是更稳健的做法。路径回溯时还有一个常见的坑不要忘了路径中包含的节点数量是dist[ex][ey] 1包含起点而方向字符的数量是dist[ex][ey]。如果你输出的是UDRL这样的移动序列只用回溯步数次如果你输出的是(x,y)坐标序列别漏掉起点坐标。4.4 从BISHI80到一类迷宫问题的模板化走迷宫的题目换个符号、换条边界条件核心逻辑基本不变。我自己平时刷题有一个习惯把BFS迷宫题抽象成一个模板一个valid函数、一个方向数组、两个二维数组dist和parent、一个主循环。之后遇到变种题目先尝试往这个模板里套套不进去的部分也就是变种引入的新逻辑单独打补丁。举个例子如果题目改为在迷宫中找一条从起点到终点的路径但是不允许朝右走你只需要把方向数组里的右方向去掉变成三个方向即可。如果题目改为每个格子有一个体力消耗值求消耗最小的路径那BFS就不再适用得换成带权最短路径算法比如Dijkstra。但如果只是加一个某些格子需要钥匙才能进入的条件BFS加一个状态维度也能搞定。这种先套模板再找差异的方法能让刷题效率提升不少。5. 实战中的坑位与调试经验5.1 死循环与队列爆炸的三大原因我在实际调试中见过最多的问题就是BFS跑不完或者连简单样例都超时。归纳下来主要原因有三个。第一个原因最基础忘记标记已访问。这里的忘记不是指完全没写而是标记的时机不对。明确一点标记必须在节点入队时立刻进行。如果等出队时才标记你看小数据可能没问题一旦迷宫变大同一个节点会被反复压入队列最坏情况下队列里同一层节点可能被重复处理几十次。排查方法是在入队的地方加一个输出语句观察入队节点是否出现重复坐标如果重复多半就是这个问题。第二个原因是边界判断写反。比如if (x - 1 0)写成if (x - 1 0)这会让最顶行无法向上移动。这类bug肉眼很难发现我建议把valid函数单独拎出来打log或者直接用几个特殊的测试用例去验证。比如起点周围全是空地看看第一步能否扩展到四个方向。第三个原因是坐标变量混乱。如果你用x、y作为当前节点坐标又用nx、ny作为新节点坐标一旦for循环里把赋值写成了x x dx[i] y y dy[i]当前坐标就被污染了整个BFS必然陷入混乱。这种错误最隐蔽因为单步看逻辑似乎正确但实际运行时同一层节点的扩展会互相影响。写代码时我给自己的规矩是当前出队节点的坐标值绝不在循环内重新赋值新节点一律用新变量接收。5.2 方向数组越界的隐蔽现场方向数组本身不易出错但它的使用场景里藏着几个隐蔽的越界问题。比如你定义了dx[4]却在循环里写到i 4这样循环的最后一次访问到dx[4]在C中是不越界检查的读出来的值是未知的内存数据轻则搜索结果错乱重则程序崩溃。我见过有人找了一整天bug最后发现只是循环条件多了个等号。另一个隐蔽的问题是memset(dist, -1, sizeof(dist))的使用。memset按字节填充-1在补码表示下全为1所以把int数组填成-1是安全的。但如果你的dist数组不是int类型而是bool类型把-1塞进去会导致所有位变为1你就失去了未访问这个状态的表达能力。这个小坑在C里特别容易踩建议记住memset只适合把int数组快速初始化为0或-1其他值一律用fill来赋。5.3 评测端常见的格式与边界坑BISHI80这类题在评测系统上跑的版本输入输出格式往往有严格约定。最常见的坑是输出没有换行符或者多了空格。有些评测系统对空白字符容忍度很高但大多数严格系统只要看到一个字符不一致就判WA。我的经验是输出cout dist[ex][ey] endl;比cout dist[ex][ey] \n;更保险其实两者等效我倒觉得\n就够了但如果你不确定用endl至少能强制刷新缓冲区在程序异常中止时输出结果也不容易丢。另有一个隐蔽的格式坑迷宫地图行内可能有空格。比如某些题目的输入格式是每个字符之间用空格隔开这样你cin grid[i]读入的就不是一整行而是单个字符。此时需要改用循环cin ch逐个字符读入。拿到题目先看清楚输入格式这是经验之谈。我早期做题时很多次WA都是因为把带空格的地图当整行字符串读了明明算法写得没有问题。5.4 用局部打印法快速定位bug调试BFS最有效的方法不是单步跟踪而是打印关键信息。我这里分享一个我常用的局部打印法在BFS主循环中每隔一层就打印当前队列的大小、队头坐标和dist数组的局部快照。观察dist数组时重点看数值的分布是否符合以起点为中心逐层递增的模式。如果某一层的dist数值出现跳变或者出现负数的未访问节点夹在中间却仍在队列里那多半是入队标记时机有问题。这个方法比断点调试高效得多因为BFS的状态变化是数万次级别的你不可能在断点下逐个确认。打印信息量不用大每处理到新的层数时输出一行就够了。很多次我排查问题就是靠看到dist[3][4]本应为2却变成了4这一条输出立刻定位到了坐标变量污染的问题。5.5 一份可自测的边界用例清单写完整份代码后不要直接提交先用几组边界用例自测。这里给出我常用的五组用例类型迷宫预期输出最小规模1x1起点即终点0直线通路1x5全是空地4完全阻挡起点被#围住-1绕路场景有墙但需绕行对应步数终点不可达终点被墙围住-1第一组和第三组经常被忽略。1x1的情况如果不加特判程序会因为起点和终点坐标重合而出错或者输出0但逻辑上BFS循环可以直接break。终点不可达时dist[ex][ey]始终是-1你直接输出-1即可。每道迷宫题的题目说明里都会写明不可达时应该输出什么有的是-1有的是NO你按题目要求来但自测时用-1先验证程序逻辑没错。6. 从BISHI80延伸出去的几个变种6.1 带钥匙的迷宫状态维度扩展如果迷宫里的某些#门需要钥匙才能打开而钥匙分布在地图各处BFS就不只是坐标层面的搜索了。此时每个状态不再是一个坐标而是坐标已收集钥匙集合。这个集合可以用位运算压缩成整型比如最多10把钥匙就用一个10位的二进制数表示。visited数组也相应变成三维vis[x][y][keyState]。BFS的框架不变但在尝试进入一个表示门的格子时额外判断当前keyState是否包含对应的钥匙位。这类问题在信息学竞赛中很常见看似复杂本质上仍然是BFS只是状态的含义变宽了。方向数组依然解决移动问题valid函数里多加一个判断而已。理解了基础BFS再理解带状态的BFS一个下午就够了。6.2 多起点或者多终点的最短逃生距离另一种常见变种是迷宫里有多个起点比如多个人需要同时逃生要求求所有起点到最近终点的最短距离。处理方法是把初始时所有起点一次性全部压入队列且dist数组全部初始化为0。这样BFS扩散时最先到达某个终点的节点就代表了距离该终点最近的那个起点。这种思路叫多源BFS在很多场景下都有应用。方向数组在这里不需要任何改动只是队列初始化的代码从压一个点变成压一堆点。6.3 输出路径字典序最小有些题目要求输出路径按字典序最小。这时方向数组的顺序就需要精心设计了。比如移动字符D、L、R、U字典序最小的是DD在L之前那么方向数组中应优先向下搜索其次向左然后向右最后向上。你需要把方向数组按字符的字典序排列这样第一个搜索到的路径就是字典序最小的路径。注意这里BFS第一次到达终点时得到的路径虽然是字典序最小的路径但这并不影响它依然是最短的因为BFS的层序特性不会因为方向顺序改变。这类细节题目描述里会明确说如果不仔细看题自己默认方向顺序很容易WA。所以拿到题目先看输出要求是任一路径还是字典序最小的路径这直接决定方向数组的排列方式。7. 经验收尾方向数组的手感是怎么练出来的做了足够多搜索题之后你会发现方向数组不只是一个技巧它更像一种编程直觉。看到一道网格题脑子里立刻浮现出dx和dy的数组内容立刻意识到这里用BFS而不是DFS立刻想到入队即标记。这些判断不是一蹴而就的靠的是反复练习形成肌肉记忆。BISHI80作为一道经典的入门迷宫题价值不在于题本身有多难而在于它把BFS的骨架、方向数组的用法、visited标记的时机、边界条件的处理这些核心技能全部揉在了一起。我建议你拿到这道题至少用三种方式各写一遍第一遍直接用我的模板AC掉第二遍不看代码自己从零实现逼自己把每一个细节都想清楚第三遍尝试加上路径输出功能把parent数组和方向字符的映射写出来。三遍写完后你基本上可以自信地面对所有同类迷宫题了。对我个人而言这题的手感是从一次一次调试死循环、一次次看dist数组的打印输出中磨出来的。走迷宫看似简单但它教会你的严谨习惯会在之后的图论算法学习中反复受益。最后分享一个小习惯每次写完BFS我会在代码尾部保留一行注释写上// BFS: 入队即标记, 出队即扩展。这句注释看似简单却能在下次复盘时帮我快速抓住算法的核心心法。希望你也能在实操中找到属于你自己的那一句心法口诀。