企业官网建设流程全解析

第一次看到 UVa 10605 的题目名字，我以为是个模拟矿工挖钻石的小游戏，结果读题之后发现，这是一道非常典型的状态压缩 BFS 搜索题。题名里的 Mines 既可以理解成“矿区”，也可以听成“地雷阵”，恰好地图里这两种气质都有：你要在矿洞里找齐所有钻石，还得躲着不能踩的地雷。对于想练搜索、位运算和状态设计的人来说，这道题是很好的入门级实战样本。

我习惯把题面重述成下面这个版本：给定一张网格地图，入口用 S 表示，出口用 E 表示，钻石用 D 表示，地雷用 M 表示，剩下的是空地 . 和不可通行的墙 #。每一步可以向上下左右移动一格，不能走进 #，也不能走进 M。你要从 S 出发，把地图上所有 D 都走遍（踩上去就算收集），最后到达 E，问最少需要多少步。数据范围很友好，钻石数量通常不超过 12，所以不用想太多复杂优化，先想清楚怎么用状态压缩把这道题稳稳拿下。

1. 从“地雷图”到状态压缩：这道题到底在考什么

1.1 题面重述

如果你拿到的是原题，字符可能不是 S/E/D/M，这很正常。做题的第一步不是背代码，而是把“特殊格子”抽象成模型。这里真正的关键只有三条：有若干个必须收集的目标点，有若干个不能走的障碍点，有一个起点和一个终点。至于字符叫什么，真的不重要。

举个例子，假设地图是这样：

3 4 S.D. #.M. ..ED

S 在 (0,0)，D0 在 (0,2)，D1 在 (2,3)，M 在 (1,2)，E 在 (2,2)。你需要从 S 出发，先拿到两颗钻石，最后到 E。注意，M 和 # 都不能踩，所以看似很近的路可能根本走不通。这时候我们首先要判断：用平时最熟的普通 BFS，记录一个 (r,c) 坐标，能不能解决？答案是不能，原因会很直观地暴露出来。

1.2 为什么普通 BFS 会漏答案

普通 BFS 只能解决“从起点到终点最少步数”的问题，因为它的状态只包含当前位置。但在这道题里，走到同一个格子的“历史”不同，后续决策就完全不同。你可能会在 (2,2) 这个出口前面路过，但那时你还没集齐钻石，不能返回；等你集齐钻石后再绕回来，这个 (2,2) 才真正有效。

用一个生活化的例子理解：你在同一个路口，手里已经拿到外卖要去送，和还没到店里取餐，虽然站在同一个位置，但接下来要做的事完全不一样。普通 BFS 只记住“你在哪个位置”，它记不住“你已经完成了几件事”。对于要集齐多个目标的题目，少了这一维信息，就会把不同状态混在一个格子里，搜出来的最短路径很可能是错的。

1.3 数据范围早就把方向指好了

这类题的数据范围往往暗示了算法。钻石数量少，是因为要枚举“哪些钻石已经收集”这个集合。如果有 K 颗钻石，收集状态一共 2^K 种。K 不大于 12 时，2^12 只有 4096 种，配合地图规模，总状态数是“行数 × 列数 × 2^K”，整体还是可以接受的。

如果 K 是 20，2^K 直接超过一百万，再加地图维度就会非常吃力。所以看到 K ≤ 12，基本就是在说：把每一个钻石的收集情况用一个整数的二进制位表示。每一位是 0 表示还没收集，1 表示已经拿到。这比用数组 bool picked[K] 更紧凑，也更好做状态转移。

2. 状态设计是灵魂：记下位置，还要记下收集进度

2.1 一个状态三元组 (r, c, mask)

这道题的状态应该设计成三元组：当前位置 (r,c) 和当前收集进度 mask。mask 是一个整数，假设有 3 颗钻石，mask 的二进制就是 xyz，第一位代表编号 0 的钻石，第二位代表编号 1，第三位代表编号 2。某个位是 1，代表对应钻石已经在包里了。

为什么不能只用位置？因为同一个位置可能被不同收集进度的人到达。你在 (2,2) 这个格子，可能一颗钻石都没拿到，也可能已经拿了两颗。接下来能不能结束，完全取决于 mask。所以在 BFS 里，(2,2,mask=0) 和 (2,2,mask=3) 是两个独立节点，它们各自只要被第一次访问，最短步数就已经确定。

2.2 给钻石编号，用位运算记账

读取地图时，我会用一个二维数组 diamondId[r][c] 记录这个格子上的钻石是几号。如果不是钻石，就给 -1。比如第二行第三列有一块钻石，编号是 1，那么 diamondId[1][2] = 1。这样当 BFS 走到一个格子时，只要查 diamondId 就知道要不要“记账”。

“记账”的操作就是位运算。假设当前收集状态是 mask，新走到一格，该格是编号 k 的钻石。那么新状态就是：

int nmask = mask | (1 << k);

这里的1 << k是常数时间构造一个第 k 位为 1 的整数。比如只有两颗钻石，状态表长这样：

最后判断“所有钻石都收集齐”也非常直接：如果所有钻石总数是 K，那么 fullMask = (1 << K) - 1。只要某个状态的 mask == fullMask，就能确定所有目标都已经完成。

2.3 dist 数组到底在记录什么

我习惯开一个三维数组：

int dist[MAXR][MAXC][1 << MAXK];

dist[r][c][mask] 表示“走到 (r,c)，并且手里已经收集了 mask 这些钻石”所需要的最少步数。没访问过的状态初始化为 -1。因为 BFS 是逐层扩展的，第一次遇到某个状态时，dist 里记录的一定是到达该状态的最短路，不需要像 Dijkstra 那样反复更新。

要注意，dist 的第三维不是“备选”，而是必须存在的维度。如果只开二维，就会得到 1.2 里说的错误结果。反过来，也不能只用 mask 作为状态而丢掉坐标，因为移动和位置显然影响后续路径。所以 (r,c,mask) 三者一个都不能少。

3. 逐层推进：BFS 队列里的每一步在做什么

3.1 扩展规则只有四条

从队列里拿出一个状态后，我们检查四个方向。对每个方向的新格子，做四件事：

1. 检查是否越界。
2. 检查是否撞上了不可走的格子，# 和 M 直接跳过。
3. 如果新格子是钻石，把对应位加入 nmask。
4. 如果 (nr,nc,nmask) 还没有被访问过，记录距离并入队。

这些步骤顺序看起来简单，但每一步都在为后面的正确性服务。尤其是步骤 3，它必须发生在“查重”之前。原因很好理解：状态包含 mask，如果先查重再更新钻石，那么同一个格子第一次到达时即使漏掉了钻石位，也可能被错误标记为访问过，导致后续真正需要该钻石位的状态无法入队。

3.2 钻石的读取、mask 更新与判重顺序

一个常见的错误是把“走格子”和“捡钻石”分成两步，然后不小心漏掉更新。我建议这样写：

int nmask = cur.mask; if (diamondId[nr][nc] != -1) { nmask |= (1 << diamondId[nr][nc]); } if (dist[nr][nc][nmask] != -1) continue; dist[nr][nc][nmask] = curDist + 1; q.push({nr, nc, nmask});

先算出 nmask，再查重。这样即使新格子是非钻石，nmask 也等于原 mask，逻辑很统一。如果新格子是钻石但已经收集过了，mask | (1 << k)不会改变结果，重复踩同一个钻石不会出错。

3.3 出口判断放在出队而不是入队

我在写这类 BFS 时，习惯在弹出队首时检查是否到达终点，而不是在扩展邻居时检查。原因是：一个状态只有在“当前步数已经确定”的时候，检查条件才最干净。尤其当出口本身也是一个钻石格，或者你会在到达终点后又离开去补收集时，出队检查能避免很多边界情况。

具体判断条件：

if (cur.mask == fullMask && ((er == -1 && ec == -1) || (cur.r == er && cur.c == ec))) { return curDist; }

如果你拿到的原题没有出口 E，只要求“收集完所有钻石即可”，那直接把出口条件去掉，改成只要 mask 为 fullMask 就返回。这个灵活判断放在代码里，不影响有出口的情况。

4. 可运行的 C++ 代码与关键函数拆解

4.1 完整代码

下面是我按上面的模型写的一份可以直接提交的 C++ 代码。地图字符按 S/E/D/M/#/. 处理，如果你原题字符不同，只需要改预处理部分的判断条件。

#include <bits/stdc++.h> using namespace std; const int MAXR = 35; const int MAXC = 35; const int MAXK = 12; struct State { int r, c, mask; }; int R, C; string grid[MAXR]; int diamondId[MAXR][MAXC]; int dist[MAXR][MAXC][1 << MAXK]; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; int solve() { memset(diamondId, -1, sizeof(diamondId)); int sr = -1, sc = -1; int er = -1, ec = -1; int K = 0; for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { if (grid[r][c] == 'S') { sr = r; sc = c; } else if (grid[r][c] == 'E') { er = r; ec = c; } else if (grid[r][c] == 'D') { diamondId[r][c] = K++; } } } if (K > MAXK) return -1; // 如果原题没有 S，用第一个空地/钻石作为起点 if (sr == -1) { for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { if (grid[r][c] == '.' || grid[r][c] == 'D') { sr = r; sc = c; r = R; c = C; break; } } } } if (sr == -1) return -1; int fullMask = (1 << K) - 1; int startMask = 0; if (diamondId[sr][sc] != -1) { startMask |= (1 << diamondId[sr][sc]); } memset(dist, -1, sizeof(dist)); queue<State> q; dist[sr][sc][startMask] = 0; q.push({sr, sc, startMask}); while (!q.empty()) { State cur = q.front(); q.pop(); int curDist = dist[cur.r][cur.c][cur.mask]; if (cur.mask == fullMask && ((er == -1 && ec == -1) || (cur.r == er && cur.c == ec))) { return curDist; } for (int d = 0; d < 4; ++d) { int nr = cur.r + dr[d]; int nc = cur.c + dc[d]; if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; if (grid[nr][nc] == '#' || grid[nr][nc] == 'M') continue; int nmask = cur.mask; if (diamondId[nr][nc] != -1) { nmask |= (1 << diamondId[nr][nc]); } if (dist[nr][nc][nmask] != -1) continue; dist[nr][nc][nmask] = curDist + 1; q.push({nr, nc, nmask}); } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); while (cin >> R >> C) { for (int r = 0; r < R; ++r) { cin >> grid[r]; } cout << solve() << '\n'; } return 0; }

这份代码里用了bits/stdc++.h，在 UVa 的老编译器上可能需要改成包含<iostream>、<queue>、<cstring>和<string>。如果你在本地用较新的编译器，直接跑没问题。

4.2 代码中容易被忽略的三个位置

第一个位置是memset(diamondId, -1, sizeof(diamondId))。因为多组数据之间会残留上次的钻石编号，不清空的话，第二次输入时会把旧编号带到新地图上，导致 mask 更新错乱。第二个位置是起点如果本身就是钻石，必须把 startMask 的对应位也置 1。否则你明明站在钻石上，初始状态却没记录，下一步再走回来才能拿到，答案会偏大。第三个位置是K > MAXK的判断。如果钻石数量超过数组第三维能装的大小，直接返回 -1 都比崩栈强。

4.3 一个我本地验证过的小样例

就拿前面那张地图：

3 4 S.D. #.M. ..ED

输入到程序里，输出是 8。具体路径是：S → (0,1) → (0,2) 拿钻石 → (0,1) → (1,1) → (2,1) → (2,2) → (2,3) 拿第二颗钻石 → (2,2) 出口，一共 8 步。这个样例很好地说明了为什么必须引入 mask：你第一次走到 (2,2) 时大概第 6 步，但那时钻石还没拿完，不能结束；绕到 (2,3) 再回来，步数就变成了 8。

5. 踩坑复盘：提交时最容易翻车的几个细节

5.1 拿到了新钻石，却忘了更新 mask

这是我第一次写这道题时犯过的错误。当时我在扩展函数里先判断了dist[nr][nc][cur.mask]是否访问过，然后再去检查钻石。结果地图上只要有钻石，第二次到达同一点概率极低，但状态本身是错误的。正确做法必须是“先更新 mask，再查重”，因为 mask 是状态的一部分。把这一行漏掉，很可能因为样例太弱而看不出来，但提交上去就会在一些边界数据上 WA。

5.2 把地雷 M 当成了普通空地

题目里的 M 是不可进入的雷区。如果你抱着“都叫 Mines，应该可以踩吧”的想法，那搜索出来的最短路会误穿地雷。尤其当 M 出现在比较窄的通道上时，可能你为了省两步就直接踩进去，结果答案比正确答案短，一提交就是 Wrong Answer。

5.3 多组输入和第二维/第三维数组的初始化

多组数据的坑很经典。如果上一组的地图比这一组更大，dist 数组里残留的旧距离不会自动消失。我建议每组数据都做一次全量memset，不要偷懒只初始化当前 R 和 C 的范围。因为访问状态时使用的是完整坐标范围和 mask 范围，旧数据很容易被访问到。diamondId同理，必须每次清成 -1。

5.4 加上 K > MAXK 的保护，防止数组越界

由于 dist 第三维大小是1 << MAXK，如果实际钻石数量大于 MAXK，状态数会超过数组容量。虽然题目大概率不会这么设计，但加一行保护可以让你的代码在遇到异常输入时不会直接崩溃。这不是核心逻辑，但能体现你对边界条件的敏感度。

6. 从这道题延伸：经典模型、变式和个人扩展思路

6.1 它和旅行商问题其实是亲戚

本质上，这道题要解决的是“以最优顺序访问多个目标点”的问题，和旅行商问题的目标很像。区别在于，旅行商问题通常给你一张完整的带权图，而这里的地图本身就是网格，移动代价是 BFS 的层数。如果你把每颗钻石之间的最短距离先用 BFS 算出来，再用集合 DP 求最优访问顺序，也能得到同样的答案。

两种做法各有优势。直接在原图上跑状态压缩 BFS，写起来简单，尤其适合障碍格子多、图结构复杂的题。先预处理距离再做 DP，适合目标点之间较长且地图较大的情况，因为可以把图压缩成 K+2 个点的小完全图。理解这道题的 BFS 写法，之后再去看那类 DP，会有一种“原来就是换了个表达方式”的感觉。

6.2 常见变式：返回起点、任意出口、带权移动

如果题目改成“收集完所有钻石后必须回到起点”，只需要把出口判断改成判断位置等于起点就可以。如果改成“到达任意出口即可”，那就把所有出口都记下来，在出队时检查当前位置是否在出口集合里。如果移动代价不是每一步都是 1，比如有不同地形，BFS 就要换成 Dijkstra 或 0-1 BFS，但状态设计依然是 (位置, mask)。

这些变式看似很多，核心并没变。只要“位置 + 收集进度”这个状态空间能被完整枚举，剩下的就是用什么样的最短路算法在这个状态图上跑。

6.3 把“状态压缩 BFS”模板迁移到其他题

我后来做很多带“必须访问目标点”的搜索题，都会先问自己三个问题：目标点有几个？每个目标点能不能用一位二进制表示？状态里除了位置还需要哪些进度信息？只要这三个问题想清楚，代码骨架几乎不用变。先定义一个 State struct，再写扩展函数，最后套 BFS，今天这个模板就能直接用了。

我自己在实际刷题时，还会刻意把dist数组的第三维注释写成“mask”，提醒自己这不是什么神秘优化，而是记录“已经发生过哪些关键事件”。希望这篇复盘能帮你把状态压缩 BFS 这个模板真正吃透，而不是只背下来一段代码。