第一次看到 H.Maze 这个题名的时候，我以为它又是一道普通的 BFS 迷宫题：给一张网格图，从 S 走到 E，模板一抄就能过。直到我在某高校软件与微电子学院程序设计竞赛的榜单上看到这道题卡住了一大批人，才反应过来，事情没那么简单。H.Maze 的核心不在于“走迷宫”，而在于“带着状态走迷宫”——网格里散落着 6 种钥匙和对应的门，你可能会为了拿钥匙绕路，绕完路还要回到之前走过的地方，这时候二维判重就完全失效了。这就是典型的状压 BFS。今天这篇博文从题意拆解、解法推导、完整代码到避坑经验，把这题完整复盘一遍，适合刚学搜索、想搞懂状态压缩 BFS 的选手，也适合笔试面试前突击复习迷宫类题目的人。
1. 题目到底在考什么：先还原 H.Maze 的原貌
1.1 一个不会写代码也能看懂的迷宫设定
H.Maze 本质上是一个带条件的网格最短路问题。场景大致是这样：有一个 n 行 m 列的网格图，格子一共分几种：
.：空地，可以走。#：墙壁，不能走。S：起点，只有一个。E：终点，只有一个。a到f：6 种钥匙，走到这个格子自动获得对应钥匙。A到F：6 种门，只有持有对应的小写钥匙才能通过。
每走一格消耗 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。
| 当前持有的钥匙 | 二进制表示 | 十进制 |
|---|---|---|
| 无 | 000000 | 0 |
| 只有 a | 000001 | 1 |
| 只有 c | 000100 | 4 |
| 同时有 a 和 c | 000101 | 5 |
| 同时有 a 和 f | 100001 | 33 |
在代码里，这个集合的操作非常自然：
- 检查有没有钥匙 b：
key & (1 << 1) - 拾取钥匙 b：
key | (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) { queue<Node> 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 题，而是帮你打通状态压缩思路的一道好题。
