状态压缩BFS详解：用位运算解决带钥匙迷宫最短路径

第一次看到 H.Maze 这个题名的时候我以为它又是一道普通的 BFS 迷宫题给一张网格图从 S 走到 E模板一抄就能过。直到我在某高校软件与微电子学院程序设计竞赛的榜单上看到这道题卡住了一大批人才反应过来事情没那么简单。H.Maze 的核心不在于“走迷宫”而在于“带着状态走迷宫”——网格里散落着 6 种钥匙和对应的门你可能会为了拿钥匙绕路绕完路还要回到之前走过的地方这时候二维判重就完全失效了。这就是典型的状压 BFS。今天这篇博文从题意拆解、解法推导、完整代码到避坑经验把这题完整复盘一遍适合刚学搜索、想搞懂状态压缩 BFS 的选手也适合笔试面试前突击复习迷宫类题目的人。1. 题目到底在考什么先还原 H.Maze 的原貌1.1 一个不会写代码也能看懂的迷宫设定H.Maze 本质上是一个带条件的网格最短路问题。场景大致是这样有一个 n 行 m 列的网格图格子一共分几种.空地可以走。#墙壁不能走。S起点只有一个。E终点只有一个。a到f6 种钥匙走到这个格子自动获得对应钥匙。A到F6 种门只有持有对应的小写钥匙才能通过。每走一格消耗 1 步问从 S 到 E 的最短步数如果永远到不了就输出 -1。这里有个容易被忽略的设定每个钥匙的图标是独立的小写字母门是大写字母。拿到钥匙后不需要“消耗”它只要一直带在身上对应的门就可以反复通过。也就是说钥匙本质上是一个“持有集合”而不是数量库存。有的版本会把地图规模限制在 n, m ≤ 100钥匙种类就是 26 个字母中的 6 个。这组约束不是随便给的它直接决定了后面用什么算法、开多大的数组。如果地图很大而钥匙又很多题目性质就完全变了。1.2 为什么这题值得单独写一篇复盘H.Maze 在比赛里被放在 H 这个位置难度卡得很有意思。它没有考高级数据结构也没有考复杂的数学推导核心就一个点你会不会把“持有钥匙的集合”当成状态的一部分。会这个思路的人代码二十行就能写完不会的人用普通 BFS 写出来怎么跑都是 WA甚至小样例能过一上大数据就崩。这类题在正式笔试和面试里也是常客只是换了一张皮。可能是“开门取钥匙”可能是“收集道具开机关”也可能是“推箱子”。套路都是同一个当你在图上游走时除了坐标之外还有一组很小的额外状态这组状态会改变你后续能走的路。这时普通 BFS 的二维 visited 数组就不够了必须把额外状态压进状态空间。2. 从“会超时”到“不超时”解法推导的关键一步2.1 朴素二维 BFS 到底错在哪先看一个最简单的反例。假设地图长这样S . # . . . a . # A . . . . . E起点在左上角钥匙 a 在地图右上区域门 A 在中下方终点 E 在右下。要开门拿钥匙玩家必须先走到钥匙 a 那里再原路返回向下穿过门 A。问题来了普通 BFS 用二维 visited 数组记录“这个格子有没有被访问过”搜索过程中先一步走到了中间那个空地上并且给它打了标记。等到拿到钥匙 a 想原路回来、再从这块空地继续向下走的时候BFS 一看这个格子 already visited直接跳过。于是从这块空地到门 A 的后续路径就永远丢失了。这里的本质是BFS 认为“同一个格子只要被访问过一次就不再需要访问”。但在带钥匙的迷宫里两次走到同一个格子的人手里持有的钥匙可能完全不同。第一次经过空地时没有钥匙开不了门第二次带着钥匙再经过空地时已经可以去开门了。这两个时刻虽然坐标相同但是状态不同对后续路径的影响也不同不能混为一谈。2.2 状态压缩用一个二进制数记住钥匙集合既然问题出在状态漏掉钥匙集合那就把钥匙集合加进状态里。钥匙最多 6 种每种只有“有”和“没有”两种情况刚好可以对应二进制位。设定第 0 位表示是否持有钥匙 a第 1 位表示是否持有钥匙 b依此类推到第 5 位表示钥匙 f。当前持有的钥匙二进制表示十进制无0000000只有 a0000011只有 c0001004同时有 a 和 c0001015同时有 a 和 f10000133在代码里这个集合的操作非常自然检查有没有钥匙 bkey (1 1)拾取钥匙 bkey | (1 1)开 b 门后如果钥匙不消耗集合不变如果题目说钥匙会消耗就再执行key ~(1 1)这就是“状态压缩”的名字来源本来要开一个数组记录 6 种钥匙的存在情况现在只用一个 int 就够了。2.3 新状态下的 BFS复杂度其实很低把“坐标 钥匙集合”看作一个完整状态记作(x, y, key)。其中 key 的取值范围是 0 到 63一共 64 种。那么整个搜索空间的大小就是n * m * 64n 和 m 都是 100 的话状态总数是 100 * 100 * 64 640000。每个状态向四个方向扩展总操作数大约在 250 万量级对 C 来说毫秒级就能跑完。判重数组也可以直接开成三维 bool 数组bool vis[105][105][64];这个数组占用的内存约 0.6 MB非常安全。对比一下如果不做状态压缩而是在每个节点存一个完整的钥匙数组代码会变得很难写判重也很麻烦。用二进制压缩之后不管是判断、更新还是查重全部变成位运算效率高代码也短。3. 一步步实现从建图到出答案的完整代码3.1 数据结构先想清楚再动手状态我用一个结构体包装struct Node { int x, y; // 当前坐标 int key; // 当前持有的钥匙集合bitmask int step; // 已经走的步数 };很多初学者会问为什么不用二维 step 数组记录步数因为这里的“状态”已经变成三维了如果用数组记录步数理论上要开step[x][y][key]开三维数组也能写但结构体直接携带 step 会更直观逻辑也更不容易错。队列里每扩展一个新状态就在原来步数上加一。方向数组和地图数组没有特别之处const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1};3.2 扩展时的判定顺序终点必须先于门这是整个代码里最容易翻车的地方。走到一个新格子(nx, ny)后判定顺序应该是越界判断墙壁判断是否为终点 E如果是直接返回当前步数加一判断大写字母门看钥匙够不够判断小写字母钥匙更新集合查重入队。为什么终点 E 的判断要排在门之前因为 E 这个字符恰好属于大写字母 A 到 F 的范围内。如果代码写成“只要是大写字母就当门处理”那么终点 E 就会被误判成需要钥匙 e 才能通过的门。地图里如果没有 e 钥匙或者玩家还没拿到 e 钥匙BFS 永远扫不到终点最后只能输出 -1。这不是题目规则完全是实现细节的坑。3.3 H.Maze 核心代码带注释#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXM 105; int n, m; char mp[MAXN][MAXM]; bool vis[MAXN][MAXM][64]; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; struct Node { int x, y; int key; int step; }; int bfs(int sx, int sy) { queueNode q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] true; while (!q.empty()) { Node cur q.front(); q.pop(); for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (mp[nx][ny] #) continue; // 终点优先判断E 虽然是大写字母但不是门 if (mp[nx][ny] E) { return cur.step 1; } int nk cur.key; // 大写字母 A-F 是门检查对应钥匙 if (mp[nx][ny] A mp[nx][ny] F) { int need mp[nx][ny] - A; if (!(nk (1 need))) continue; } // 小写字母 a-f 是钥匙拾取并更新集合 if (mp[nx][ny] a mp[nx][ny] f) { int id mp[nx][ny] - a; nk | (1 id); } if (vis[nx][ny][nk]) continue; vis[nx][ny][nk] true; q.push({nx, ny, nk, cur.step 1}); } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); while (cin n m) { memset(vis, 0, sizeof(vis)); int sx 0, sy 0; for (int i 0; i n; i) { cin mp[i]; } for (int i 0; i n; i) { for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } } } cout bfs(sx, sy) \n; } return 0; }代码里mp[i]用字符串读入天然解决了换行符问题。如果题目有多组测试数据memset(vis, 0, sizeof(vis))在每一轮开始执行一次即可。3.4 用一个小样例把流程走通我们拿一个极小的地图来验证逻辑S a A . . E起点在左上角a 钥匙在起点右边A 门在钥匙右边终点在右下角。正确路径是向右走到 a 拿钥匙再向右穿过 A 门最后向下到达 E共 3 步。代码执行时BFS 从起点开始第一轮扩展发现右边是 a更新 key 为 1入队第二轮扩展发现右边是 A检查 key 的第 0 位为 1允许通过第三轮扩展发现下方是 E直接返回步数 3。整个过程非常顺。如果代码里少了“先判终点”这个逻辑这个样例就直接变成不可达。实测中这是 WA 率最高的一类原因。4. 比赛现场踩过的坑从 WA 到 AC 的排查清单4.1 终点 E 被当成门最经典的逻辑 Bug这个问题在 3.2 里已经重点提过。这里再强调一次因为它实在太隐蔽了。E 是大写字母而门的范围是大写 A 到 F。很多人在写if (c A c F)的时候下意识觉得终点已经处理过了实际上代码顺序不对就会撞上。我自己的习惯是凡是地图里出现特殊角色的字母先处理特殊角色再处理通用规则。这不是这个题特有的细节很多网格题里都有类似情况例如终点用 T、起点用 K 等。规则判断的顺序一旦写错调试很久都找不到原因。4.2 判重时机不对出队时标记会导致队列爆炸BFS 判重有两个时机入队前标记或出队时标记。如果选择“出队时标记”同一个状态可能在队列里被推入多次因为它在第一次入队后还没有被标记后续扩展又发现了它。这个问题在普通二维 BFS 里可能只是多搜几层但在状态压缩 BFS 里会非常致命64 万状态上限看似很小但同一状态被重复推入几十遍队列内存会指数膨胀轻则 TLE重则 MLE。正确写法是一旦确定新状态合法立刻vis[nx][ny][nk] true再入队。这样每个状态只会入队一次队列大小严格受状态总数限制。4.3 钥匙状态没有先更新就查重扩展新格子时如果格子是钥匙要先更新nk再去看vis[nx][ny][nk]。有些代码写成先查vis[nx][ny][cur.key]结果等于拿旧钥匙集合去查重导致拿完钥匙后的新状态被误判为“已访问”直接跳过。这个问题在样例里往往测不出来因为样例路径简单大数据一跑就发现很多合法路径被剪掉了。4.4 位运算优先级和多组数据残留C 里位运算的优先级比较低特别是和混写时容易翻车。比如检查是否持有门对应的钥匙// 错误写法 if (key (1 need) 0) ... // 正确写法 if (!(key (1 need))) ...不加括号时表达式的解析顺序不是你想的那样轻则编译告警重则逻辑全错。这类 Bug 很难肉眼发现建议从一开始就写成带括号的完整形式。多组数据时除了vis数组要重置还要注意队列是否在bfs函数内部定义。如果队列定义成全局变量每次开始前必须清空否则上一组数据的状态会混进下一组。4.5 一份现场定位用的速查表现象常见原因排查方向小样例能过大数据 WA终点 E 被门规则拦下检查判定顺序运行时间爆炸出队时标记 visited改为入队前标记内存超限同一状态重复入队检查 vis 更新位置输出一直是 -1钥匙状态没纳入判重检查 vis 维度部分可开门路径丢失钥匙更新后未替换 key 再查重先更新 nk 再查 vis位运算判断错误没加括号统一写成!(key (1 i))5. 赛后复盘这题的价值不在题目本身5.1 什么样的题要想到状压 BFS吃透 H.Maze 之后最重要的是形成条件反射看到“网格最短路 少量额外状态”立刻想到状态压缩。这里的“少量”通常指不超过 20 种可枚举的选项在竞赛题里最常见的就是钥匙、道具、开关状态、已访问的怪物数量等。判断依据很简单如果普通 BFS 的 visited 数组只记录坐标而行走过程中有些路线需要“先绕远拿东西再回来走原本已经过的格子”那就是吃状态压缩的场景。遇到这种情况不要犹豫直接拿位运算压缩状态。如果额外状态的数量超过 20不能再压进一个 int这时候考虑用unordered_map做状态哈希或者重新审视题目是否有更简单的数学解法。H.Maze 之所以用 6 种钥匙就是在明示你可以用 64 这么大的状态空间去压。5.2 这个模型能延伸到哪里状态压缩 BFS 的模型非常通用。稍微改一改就能套进很多变种题传送门地图里散落传送点走上去瞬移到固定位置。BFS 扩展时多加一个“传送”行为步数算一格注意别在传送点来回死循环。火势蔓延火每秒向四周扩散玩家必须在火到达前离开状态里要多记录时间维度或者先预处理每个格子的起火时间。多把钥匙开一道门比如 A 门需要同时持有 a 和 b 两把钥匙检查时把两个位一起判断。钥匙会消耗开门时把对应位清零。这种情况下路径规划会更复杂因为同一把钥匙可能要在多个门之间取舍。多终点或出口随机BFS 扩展时遇到任意一个终点即可返回。这些变种搜的解法思路完全一致只是状态的定义和转移条件不同。5.3 练习建议和个人体会如果这题让我重新做一遍我会建议按这个顺序去写先老老实实写一个普通二维 BFS 跑样例然后画一个“绕路拿钥匙”的反例体会 visited 数组丢失信息的过程再改成三维状态。不要一上来就盯着位运算的细节先想清楚状态动手写代码就非常快。我个人的习惯是debug 时在入队的地方临时加一行打印输出(x, y, key, step)。很多隐藏问题一眼就能看出来。比如钥匙集合突然变成 0那肯定是状态更新漏了比如同一个(x, y, key)出现了两次那肯定是判重时机没对上。状态压缩 BFS 的代码量不大真正花时间的永远是状态设计。最后说一个从这场比赛里得到的体会不要把“迷宫题”和“BFS 模板题”划等号。题目名字叫 Maze它可能只是借了一张图真正考的是你在图上处理额外状态的能力。想通这一点H.Maze 就不再是卡住你的 H 题而是帮你打通状态压缩思路的一道好题。