程序设计竞赛的题单里凡是带 Maze 的题目我原先都有一个偏见要么是 BFS 入门题要么是 DFS 签到题。直到某高校软件与微电子学院程序设计竞赛的 H.Maze 教我重新做人我才意识到哪怕题目叫 Maze也可以把状态压缩、位运算、分层图这些进阶概念全部装进去。这篇文章不打算复述官方题解而是把我从读题、错解、正解到调试的完整过程写出来尤其是那些只有实际敲过代码才会踩到的坑。适合刚学会 BFS、想进阶状态搜索的选手也适合在校赛前临时抱佛脚的队友们。先说结论H.Maze 不是普通迷宫而是一个带钥匙和门的最短路问题。地图上散布着若干小写字母钥匙以及对应的大写字母门玩家从起点出发走到终点每走一格耗时为 1求最短耗时。钥匙种类数不超过 10地图行列规模可以到 100。看起来只是给 BFS 加了一个判断但如果你只用二维 vis 数组标记坐标必错。至于为什么错、怎么改下面从头讲。1. 比赛当天H.Maze 是怎么把我骗进去的1.1 题面简单到像送分实则暗藏状态比赛开始后我习惯性地从后往前翻题看到 H.Maze 时心里松了一口气。Maze 嘛无非是#是墙、.是路从走到^BFS 一套带走。等仔细读完题面才发现地图里还有一堆小写字母a、b和大写字母A、B。小写是钥匙大写是门钥匙和门按字母一一对应没有对应的钥匙门就是实心墙。题面的输入格式大概是这样的2 3 .a #A^第一行是行数 n 和列数 m接下来 n 行是地图。这个例子里是起点^是终点a是一把钥匙A是这道门。人能上下左右移动走一格耗时 1拿钥匙不额外耗时求从到^的最短耗时时长。如果到不了就输出 -1。地图的范围 n,m 不超过 100钥匙种类不超过 10。看到这个数据范围我的第一反应是 BFS毕竟 100 乘 100 的网格普通 BFS 只需要扫一遍。但是问题来了门会挡住路想开门得先找到钥匙而钥匙往往在门的另一侧。换句话说路径可能需要在某些格子上来回“折返”先过去拿钥匙再绕回来开门。这时候普通 BFS 那套“每个格子只进队列一次”的规则就不成立了。1.2 为什么第一个 BFS 版本 WA 得莫名其妙我最初提交的版本很简单队列里存坐标和步数撞到门就检查有没有钥匙没有就跳过遇到钥匙就标记已持有。测样例的时候前几个小样例全过提交却一直 Wrong Answer。直到我手动构造了一个小地图才发现问题有多隐蔽。就以上面的地图为例起点(0,0)终点(1,2)钥匙a在(0,2)门A在(1,1)。普通 BFS 的过程是这样的从起点(0,0)出发扩展到(0,1)。从(0,1)扩展左右都看过下方是门A手上没有钥匙跳过。右边是(0,2)进入队列标记(0,2)已访问。取出(0,2)拿到钥匙a然后尝试往回走到(0,1)。发现(0,1)已经被访问过。按照普通 BFS 的去重逻辑这个格子不会再次入队于是路径断在这里。最终 BFS 找不到终点输出 -1但正确答案应该是 4 步(0,0) - (0,1) - (0,2) - (0,1) - (1,1) - (1,2)只不过其中(0,1)被走了两次。第二次经过它的时候手里已经多了钥匙这个信息在普通 BFS 里完全没被记录下来。所以这道题的核心就浮现了决定下一步能不能走的不只是当前坐标还有当前手里有哪些钥匙。同一个格子没钥匙和有钥匙是完全两个状态。普通 BFS 的 vis 数组只记录“这个坐标来过没有”相当于默认每个人在任何时候能力都一样这在 H.Maze 里显然不成立。2. 正解的核心把“持有物集合”变成一维状态2.1 从三维空间理解状态转移既然只记录坐标不够那就把“当前持有哪些钥匙”也当成状态的组成部分。于是每个搜索节点从二元组(x, y)变成三元组(x, y, keyMask)。这里的keyMask是一个整数用二进制表示钥匙集合第 i 位是 1 就代表手里有第 i 种钥匙是 0 就代表没有。举个例子假设地图里最多出现 10 种钥匙编号从 0 到 9。初始状态一把钥匙都没有keyMask 0。如果捡到第 2 把钥匙keyMask变成二进制100也就是十进制的 4。如果之后又捡到第 0 把钥匙keyMask变成101表示同时持有第 0 把和第 2 把。BFS 的队列节点就变成了struct Node { int x, y; int keyMask; int step; };访问标记也从二维变成三维bool vis[N][M][1 10];vis[x][y][mask]表示“坐标(x,y)且持有钥匙集合为mask”这个状态是否访问过。一个坐标可以在不同 mask 下被多次访问因为“没钥匙的(0,1)”和“有钥匙的(0,1)”是两种局面需要分别记录。搜索转移时还是向上下左右四个方向走但多了一步判断如果新格子是普通空地或起点直接走。如果新格子是钥匙a到j需要在keyMask里把对应位置成 1。如果新格子是门A到J必须检查keyMask对应位是否为 1是才能进否则跳过。每次移动步数加 1。因为 BFS 是逐层扩展的所以第一次到达终点时的步数就是最短步数。用“分层图”来理解会更直观把整个地图复制成2^k层每一层对应一种钥匙集合。拿钥匙相当于从当前层跳到更高层开门相当于只允许拥有对应层权限的人通过。BFS 就是在这些层之间找一条从起点层到某个终点层的最短路。2.2 位运算压缩钥匙集合的边界条件有了keyMask对钥匙和门的操作就全部落在位运算上。整理一下就是这张表操作场景位运算写法说明初始状态keyMask 0没有任何钥匙检查是否有第 i 把钥匙keyMask (1 i)结果非 0 说明持有拾取第 i 把钥匙keyMask (1 i)拿到重复钥匙keyMask不变仍需通过 vis 防止重复入队这里有几个容易忽略的边界条件。第一地图里可能出现多把同名钥匙走到第二把钥匙时keyMask不会发生变化所以必须要靠vis[x][y][mask]来拦掉重复状态否则同一个“坐标钥匙集合”会反复入队效率会变得很低。第二起点和终点本身也可能是钥匙格或门格题目一般会避免这种情况但写通用代码时最好在初始化和终点判断前做一次处理别漏掉起点自带的钥匙。第三所有钥匙都拿全不一定最优。有时候直接绕过门走一条更远但不用拿钥匙的路可能反而更快所以不能等到keyMask全满才放行终点只要走到终点无论手里有几把钥匙都可以输出答案。3. 完整实现一份能 AC 的 BFS 模板3.1 数据结构选择与内存估算对于这类题我推荐直接用结构体表示节点不要为了省代码用嵌套 pair。结构体虽然多写几行但调试时能少受很多罪。地图用vectorstring存访问标记用三维bool数组。如果钥匙最多 10 种状态数就是n * m * (1 10)。以 nm100 为例100 * 100 * 1024约等于 1024 万bool 数组大小约 10MB这在竞赛环境下非常安全。如果用 int 数组记录最短步数要 40MB 左右也可以接受但没必要。因为 BFS 本身是逐层扩展的队列节点里已经带了step第一次访问到某个状态一定是最短步数所以只需要一个 bool 标记是否访问过不需要额外记录距离。初始化时直接用memset(vis, 0, sizeof(vis))。需要注意的是三维数组的维度顺序一定要和访问顺序保持一致否则很容易出现越界不报错但逻辑全乱的情况。我习惯统一写成vis[x][y][keyMask]相当于把位置放前面钥匙集合放后面。3.2 核心代码逐段拆解下面是我赛后整理出来的完整代码语言用 C17 风格。地图字符含义#墙、.空地、起点、^终点、a到j是钥匙、A到J是对应门。#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXK 10; struct Node { int x, y; int keyMask; int step; }; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; bool vis[MAXN][MAXN][1 MAXK]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorstring grid(n); int sx -1, sy -1, tx -1, ty -1; for (int i 0; i n; i) { cin grid[i]; for (int j 0; j m; j) { if (grid[i][j] ) { sx i; sy j; } else if (grid[i][j] ^) { tx i; ty j; } } } memset(vis, 0, sizeof(vis)); queueNode q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] true; while (!q.empty()) { Node cur q.front(); q.pop(); int x cur.x; int y cur.y; int curKey cur.keyMask; int curStep cur.step; if (x tx y ty) { cout curStep \n; return 0; } for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; int nextKey curKey; // 如果是钥匙先收集 if (grid[nx][ny] a grid[nx][ny] j) { int keyIdx grid[nx][ny] - a; nextKey | (1 keyIdx); } // 如果是门检查是否有对应钥匙 if (grid[nx][ny] A grid[nx][ny] J) { int keyIdx grid[nx][ny] - A; if (!(nextKey (1 keyIdx))) continue; } if (vis[nx][ny][nextKey]) continue; vis[nx][ny][nextKey] true; q.push({nx, ny, nextKey, curStep 1}); } } cout -1 \n; return 0; }代码逻辑顺序很关键先判断越界和墙再处理钥匙再处理门最后才做访问标记。先拿钥匙再判断门是一个稳妥的习惯。因为极端情况下如果某个格子既是钥匙又是门理论上应该先让玩家拿到钥匙再用新钥匙判断能不能开门。curStep代表到达当前节点已经走的步数起点为 0。每扩展一个相邻格子步数加 1。如果在终点出队时直接输出curStep就不需要额外加 1。这样处理清晰也避免样例输出对不上的问题。3.3 复杂度分析与优化空间时间复杂度很容易算状态总数是n * m * 2^k每个状态向四个方向扩展所以最坏情况是O(4 * n * m * 2^k)。当 nm100、k10 时大约需要扩展 4000 万次。C 在这种数据规模下通常能在一秒左右跑完队列操作的开销不会成为瓶颈。如果钥匙种类数还能继续增大就需要考虑优化。一个常见优化是提前把地图里的钥匙种类离散化只给实际出现的钥匙编号不要留 10 位的上限。另一个优化是终点提前返回如果当前出队的节点已经到达终点直接输出后面的状态就不用再扩展了。虽然并不能把最坏复杂度降下去但随机数据下通常能省不少时间。还有一个思路是用双端队列处理带权边但 H.Maze 每次移动代价都是 1普通队列就够了。不要在没有额外代价的情况下强行上 Dijkstra反而增加常数。真正需要注意的反而是别把vis检查放在钥匙处理之前否则会出现“第一次经过某个钥匙格时状态没更新之后再回来又被判重”的连锁 Bug。4. 复盘那些 WA 和 TLE比 AC 本身更值钱4.1 数组维度顺序导致的隐蔽 Bug我在比赛时被一个很低级的错误卡了接近二十分钟。当时觉得状态压缩的思路已经对了代码逻辑也看不出问题但就是不断 WA。后来对照别人代码一行一行看才发现三维数组的维度顺序写反了。我写的是bool vis[1 MAXK][MAXN][MAXN];但访问的时候写的是vis[nx][ny][nextKey]C 数组在内存里按行优先存储访问vis[nx][ny][nextKey]时实际会按照第一维nx、第二维ny、第三维nextKey来寻址。如果第一维声明成了1 MAXK而实际传入的nx最大才 100没越界可当nextKey最大到 1023 时它会被当成第二维和第三维的索引去计算这就完全错位了。更可怕的是编译器不会报错因为下标本身没有超出剩余维度的乘积程序照常跑但访问的是完全无关的内存区域。这种问题只能靠规范和自查来避免。我的建议是把维度固定成vis[x][y][mask]三层的含义从前往后分别是“行、列、钥匙状态”。再配上结构体成员名比如cur.x、cur.y、cur.keyMask让代码读起来一目了然。不要图省事用a[x][y][z]这种无意义命名比赛高压下很容易把自己绕晕。4.2 重复入队、门与钥匙重叠的边界处理第二个隐蔽的坑是对“重复钥匙”的处理。假设地图里有两把a钥匙玩家已经拿过一把再踩到第二把时nextKey和curKey完全相同。如果你把vis[nx][ny][nextKey]的检查写漏了同一个状态会被反复入队无限扩展轻则 TLE重则队列爆炸。处理方式很简单无论nextKey是否变化都要统一走一次vis检查和入队流程。vis拦的是“坐标钥匙集合”这个完整状态不是单纯拦坐标所以重复钥匙会自然被去重。还有一个更考验人品的边界如果题目没说钥匙格和门格不会重叠最稳妥的写法是把“拾取钥匙”放在“检查门”之前也就是我代码里的顺序。否则当某个格子同时是门A和钥匙a时先检查门会发现手里没钥匙而跳过玩家永远拿不到格子上的这把钥匙形成逻辑死锁。起点和终点也不能忽略。如果起点位置本身是一把小写字母钥匙入队前初始化keyMask时就要把它算进去。如果终点被门锁住还要检查终点判断前是否做了开门判断。大多数题面不会把终点设成门但用模板代码时最好是提前扫一遍地图把所有可能出现的异常位置都考虑进去。4.3 对拍生成随机数据的土办法样例通过并不是终点很多 WA 都是题目给的样例覆盖不到的特殊情况。我的习惯是写一个暴力搜索程序去对拍尤其是这种带状态的地图题。暴力程序不需要优化直接用 DFS 枚举所有状态同样用(x, y, keyMask)做记忆化搜索所有可能路径取到达终点的最小步数。因为数据规模很小哪怕慢也完全没关系。然后写一个随机数据生成器随机生成 n 和 m范围取 1 到 6。随机生成地图随机放墙、空地、起点和终点。随机选 k 种钥匙和 k 扇门保证地图上成对出现。把地图同时喂给暴力程序和状态压缩 BFS对比输出。对拍几百组之后基本能把写错的维度顺序、漏掉的钥匙判断全都揪出来。这个方法看起来土但确实是我在竞赛里最信任的调试手段。尤其是题目没有官方评测数据给你看时构造小数据自己去对拍比盯着代码干瞪眼有效得多。5. 这道题留给我的算法工具箱5.1 状态压缩 BFS 的适用范围做完 H.Maze 之后我总结出一套判断标准只要一个搜索问题里除了位置之外还存在“少量互斥或累积状态”而且这些状态能用不超过 15 个布尔位描述就可以优先考虑状态压缩 BFS。它和普通 BFS 的关键差异可以看这张表维度普通 BFSH.Maze 这种状态 BFS节点信息坐标坐标 keyMask访问数组二维三维适用条件状态只由位置决定位置之外还有额外状态复杂度O(nm)O(nm * 2^k)典型场景最短路径迷宫开门、开关灯、救火带工具判断要不要用状态压缩可以问自己一个问题如果两个人走到同一个格子他们接下来的选择是否完全一样如果完全一样普通 BFS 够了如果一个人手里有钥匙、另一个人没有后续能走的路线完全不同那就必须把持有物编码进状态。H.Maze 只是最经典的例子我后来还遇到过“携带炸弹可以炸墙”“点亮开关才能通过激光区”等变体本质都是同一个模型把额外状态塞进一个整数用位运算做转移。5.2 从竞赛题到工程问题的迁移这种建模方式也不只在校赛里有用。做导航路径规划时如果路径上有些路段需要特定权限才能进入就可以把“权限集合”编码成状态做仓储机器人调度时机器人可能要先取工具再去开箱同样是状态约束下的最短路。虽然工程里往往要加上实时障碍物、多智能体并发但核心思路仍然是“先定义状态空间再做搜索”。我自己的体会是这类题最考验的不是会不会写 BFS而是能不能快速识别出隐藏状态并把状态压缩到可以接受的空间里。H.Maze 这种“地图 钥匙 门”的模型非常典型见过一次之后下次再看到类似题目基本能直接套上模板。后来我又在校外赛里碰到过开关灯、控制水位、携带炸弹等变体每次都是先把额外信息压缩成一个整数 mask再丢进 BFS。做完 H.Maze 之后我把这套流程固定成了自己的模板先列状态再画转移最后写代码。这个习惯帮我省下大量调试时间。如果你也正在准备校赛建议别满足于 AC试着把地图改大、把钥匙增多再回来优化你的实现。那道题当时气得我差点摔键盘现在回头看反而成了我收获最大的一次训练。