企业官网建设流程全解析

1. 先把“旅游”翻译成图论语言：BFS 建模的第一步

那道编号 1996 的“旅游”题，我前后翻来覆去做了三遍，第一遍读完题面直接开写，交上去错了一半的点；第二遍老老实实画图，才发现自己把“移动一步”和“到达一个格子”这两件事混为一谈了；第三遍才把 BFS 的模板理顺，一遍过。这篇就把整个过程拆开讲，包括我当时为什么会想歪、模板该怎么搭、哪些地方最容易翻车。核心关键词其实就三个：网格地图、最短步数、广度优先搜索（BFS）。这类标题里带“旅游”“走迷宫”“最少步数”的题目，本质上都是同一套东西——把地图抽象成一张无权图，每个可走的格子是一个点，上下左右相邻能走通的两个格子之间连一条长度为 1 的边，然后求起点到终点的最短路径。

BFS 在这类问题里的地位，相当于泡面里的开水——没有它，你也能吃，但吃起来就不是那个味儿了。它解决的问题非常明确：在所有边权相同（通常都是 1）的图上，求单源最短路径。它的工作方式和往平静水面扔一颗石子一样，涟漪从起点一圈一圈往外扩，第一圈是距离 1 的所有格子，第二圈是距离 2 的所有格子，以此类推。因为扩展顺序严格按距离递增，所以任何一个格子第一次被访问到时，拿到的距离一定就是最短距离，不会再有更短的走法在后面出现。这个性质是 BFS 能用来求最短路的根本原因，也是它和 DFS 最本质的区别——DFS 只管“能走到”，不管“走得近不近”。

适合谁来读？如果你是刚学完队列和图的存储、正准备刷搜索题的新手，这篇可以当模板课来看，代码可以直接抄；如果你已经能默写 BFS，但总在细节上莫名其妙 WA（答案错误）或者 TLE（超时），那第 5 节的排查清单可能更对你胃口；如果你在准备比赛、需要快速判断一道新题该不该用 BFS、该用什么变体，第 4 节的变体对照表应该能帮你省下不少读题时间。我会尽量把每个“为什么这么写”都交代清楚，因为这类题目最坑的地方从来不是“BFS 是什么”，而是“状态怎么定义”“标记放在哪一行”“边界怎么判”这些看起来琐碎的细节。

2. 建模的核心：状态设计与搜索空间评估

2.1 为什么这道题的“点”不是坐标，而是“局面”

新手最容易犯的错，是把地图上的格子和图论里的点直接画等号。在纯网格最短路里这样没错，但“旅游”类题目往往会加一点料：有的格子是草地，走进去要多花一步；有的格子是传送门，踩上去会把你弹到另一个位置；有的题要求按顺序打卡若干个景点。一旦出现这种附加条件，一个坐标就不再足以描述你当前的处境，必须把“你在哪”和“你现在的附加状态”打包成一个整体，这个整体才是图论意义上的“点”。

我给这种打包方式起了个土名字，叫“身份证号原则”：每个状态都得有一张独一无二的身份证，只要两个状态的身份证号不同，它们在 BFS 里就是两个不同的点，必须分开记录访问标记。举个例子，如果题目里有“钥匙”机制，那么 (3, 5) 这个位置、手里没钥匙，和 (3, 5) 这个位置、手里有钥匙，是两个完全不同的状态，你不能用一个二维的vis[3][5]把它们混为一谈，否则就会出现“拿着钥匙走回原地却被判定为已访问、导致无法推开门”的诡异错误。

状态设计做完之后，紧接着要评估搜索空间有多大。这一步很多人跳过，结果写完跑出来内存爆掉。评估方法很简单：把每个维度的取值范围乘起来。假设地图是 n×m，附加状态有 k 种，那么总状态数是 n×m×k，BFS 队列最多同时装下这么多元素，vis和dist数组也得开这么大。以常见的 1000×1000 地图为例，纯坐标状态是 10^6 个，尚在可控范围；如果 k 是 4，就变成 4×10^6，这时候就得开始考虑int数组的内存开销了——一个 4×10^6 的int数组占 16MB，两个就 32MB，很多老平台的内存限制是 64MB 或 128MB，稍不注意就踩线。

2.2 边权到底是不是 1：一个必须先确认的前提

BFS 求最短路的唯一前提是边权相同。这句话我建议你抄在草稿纸最上面，因为它是判断“这题能不能直接 BFS”的唯一标准。普通的上下左右移动，走一步代价是 1，所有边权都是 1，放心用 BFS。但如果题目说“进入沼泽格需要额外消耗 2 点体力”，那从沼泽相邻格子进沼泽的这条边，权值就变成了 2，而其他边还是 1，这时候 BFS 的“按层扩展”就被破坏了，第一次访问到某个点拿到的未必是最短距离。

遇到边权不全为 1 的情况，通常有三条路可走，我在第 4 节会展开，这里先给个结论性的判断：如果边权只有 0 和 1 两种，用双端队列实现的 0-1 BFS，复杂度还是 O(V+E)，比堆优化的 Dijkstra 常数小很多；如果边权是任意正整数，老老实实上 Dijkstra；如果边权种类很少（比如只有 1 和 2），也可以把一个代价为 2 的格子拆成两个中间节点，强行把边权拉回 1，继续用普通 BFS。这三种做法各有适用面，选错了不一定 WA，但很可能 TLE。

还有一个隐蔽的坑：有些题目表面上边权都是 1，但你仔细看会发现“移动到相邻格”和“传送到指定格”这两种操作的代价不一样。这种情况下，如果传送操作只在少数几个格子上出现，可以整体用 BFS + 特殊处理；如果传送格遍地都是，那就该考虑建分层图了。

2.3 建模完成之后该做什么：先手算一遍小样例

我个人的习惯是，状态设计定下来之后不急着写代码，先在纸上跑一遍最小的样例。找一个 3×3 或者 4×4 的地图，手动用队列模拟 BFS 的扩展过程，把每一层的格子标上数字，看看扩展顺序对不对、终点是不是在最早的那一层被碰到。这个过程大概花三到五分钟，但能提前暴露大概一半的逻辑错误，比如方向数组写反、边界判断漏了一侧、起点忘记初始化距离。

手算还有一个额外好处：它能帮你确认题目的答案是“步数”还是“经过的格子数”。这两个东西在某些题目的定义下差 1，我见过太多人代码逻辑完全正确、就因为输出的时候没加或没减这个 1，硬生生错掉一半测试点。手动跑一遍样例，把样例的输入输出和自己的手算结果对齐，这个 1 到底是加还是不加，一目了然。

3. 模板骨架：一份可以反复套用的 BFS 实现

3.1 队列、vis、dist 三件套的职责划分

一份干净的 BFS 代码，骨架永远是三样东西：队列、访问标记、距离数组。它们各自的分工必须清楚，混用就会出问题。队列负责维护“待扩展的边界”，也就是当前这一层以及下一层的候选点；vis负责回答“这个点以前有没有进过队列”，防止同一个点被反复入队导致队列爆炸；dist负责记录“从起点到这个点的最短距离”，如果题目只问可达性，可以省掉它。

关于vis和dist能不能合并，我的建议是能合并就合并，但要看清楚语义。如果距离数组初始化为 -1，那么dist[x][y] != -1本身就等价于“已访问”，一个数组干两件事，代码更短，也不容易出现两个数组更新不同步的问题。但如果距离的合法取值包含 -1（比如某些带负权的特殊题目），那就必须分开。合并的时候还要注意初始值的选择：memset(dist, -1, sizeof(dist))对int数组是安全的，因为 -1 的二进制是全 1，但如果用memset给long long数组赋 0x3f 之类的值，就得小心字节填充的问题，稳妥写法是用fill或者手写循环。

3.2 方向数组：四方向和八方向的写法取舍

网格题的方向扩展，我推荐用两个常量数组dx[]和dy[]配合一个循环，而不是写四段几乎一样的 if 分支。原因很实际：写四段 if 的时候，你极有可能在复制粘贴的过程中把某一行的加减号写反，而这种错误编译器完全不管，只能靠测试数据抓，抓不抓得到全看运气。用方向数组就不一样了，方向对不对一眼就能看出来，改起来也只改一行。

四方向的经典写法是：

const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1};

这四组分别对应上、下、左、右。如果你需要八方向（含对角线），就在后面补上{-1,-1}, {-1,1}, {1,-1}, {1,1}这四组，注意顺序要和dy严格对应，别错位。有些题目会明确说“只能走上下左右”，有些会说“八个方向都能走”，读题时务必确认，别凭感觉。

至于边界的判断，有两种风格。一种是在循环内部用 if 判断越界，代码直观，缺点是每次都要写四个比较。另一种是在网格外面加一圈“围墙”，把合法坐标范围从[1,n]×[1,m]扩展成[0,n+1]×[0,m+1]，然后把围墙上的格子预先标记成障碍，这样循环内部只判断“是不是障碍”就够了。后一种写法能省掉越界判断，常数略小，而且能避免“下标为负”这种在某些平台上行为未定义的坑。我个人在数据规模大的时候偏向加围墙，规模小的时候怎么顺手怎么来。

3.3 入队时标记还是出队时标记：一个决定生死的细节

这个问题值得单独拎出来说，因为它是我见过的最容易写错、而且错了之后症状最迷惑的地方。

vis的标记动作，必须放在入队的那一刻，而不是出队的那一刻。原因在于，同一个格子可能被多个不同的前驱节点同时发现。假设格子 C 同时与 A、B 相邻，BFS 从 A 和 B 分别扩展到 C，如果标记动作放在出队时，那么 A 把 C 入队、B 也把 C 入队，队列里就出现了两份 C，等它们相继出队时才被标记，队列的元素数量就会成倍膨胀。在小数据上这顶多让程序慢一点，看不出问题；但在 10^5 级别的数据上，队列可能膨胀到百万级，内存直接爆掉，或者时间超出限制。

入队即标记的写法就干净得多：A 发现 C 没被标记，立刻标记、记录距离、入队；B 再来发现 C 已经被标记，直接跳过。全程每个格子最多入队一次，队列的最大长度不会超过状态总数。这个细节看似只是挪了一行代码的位置，实际上决定了你的程序能不能在数据规模上活下来。

提示：vis标记、dist赋值、push入队，这三件事必须挨在一起写，中间不要插入任何其他逻辑，否则改代码的时候极容易漏掉其中一个。

4. 完整实操：从读入到输出的全过程

4.1 数据读入与坐标系的统一

先讲读入。网格题最常见的两种输入格式：一种是一次给一个字符串，cin >> row或者scanf("%s", buf)读进来，然后逐字符处理；另一种是给 n 行 m 列的字符，字符之间可能有空格也可能没有。前一种更快也更省心，我一般统一用字符串读入，因为字符之间有没有空格、换行是 CRLF 还是 LF，这些破事用一次性读字符串的方式都能绕开。

如果地图规模到了 10^5 行这种级别，cin即使关了同步也可能不够快，这时候要么改成scanf("%s")，要么写一个快读。我自己的习惯是：只要数据规模超过 10^5 个字符，就直接上快读或者getchar手写循环，省得因为读入拖慢整个程序。

坐标系方面，我强烈建议从 1 开始编号，并把数组开大一圈。这样做的直接好处是：判断越界的时候可以用nx < 1 || nx > n这种形式，不会出现下标为 -1 的情况；加围墙的写法也更自然，围墙正好落在第 0 行、第 n+1 行这些位置上。当然，从 0 开始编号完全没问题，只是下标计算要更小心，别在某个地方漏减 1。

4.2 一份逐段注释的完整代码

下面是我现在打这类题目的通用骨架，以“网格最短路、四方向移动、# 为障碍、S 起点、T 终点”为例：

#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN = 1005; int n, m; char g[MAXN][MAXN]; // 地图，从 1 开始编号 int dist[MAXN][MAXN]; // -1 表示未访问，同时兼作 vis int sx, sy, tx, ty; // 起点与终点坐标 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; int bfs() { memset(dist, -1, sizeof(dist)); // 全部初始化为未访问 queue<pair<int, int> > q; // 队列存坐标 dist[sx][sy] = 0; // 起点距离为 0 q.push(make_pair(sx, sy)); // 入队即标记，二者不可分 while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); // 终点可以在出队时判断，也可以在入队时判断 if (x == tx && y == ty) return dist[x][y]; for (int d = 0; d < 4; ++d) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 越界 if (g[nx][ny] == '#') continue; // 障碍 if (dist[nx][ny] != -1) continue; // 已访问 dist[nx][ny] = dist[x][y] + 1; // 距离递推 q.push(make_pair(nx, ny)); // 标记与入队紧挨着 } } return -1; // 队列空了还没碰到终点，说明不可达 }

这段代码里有几个地方值得单独说。第一，if (x == tx && y == ty) return dist[x][y];放在出队之后是合法的，因为出队顺序严格按距离递增，第一个出队的终点一定是最短的那条路。如果你想再省一点，可以把这个判断挪到入队之后立刻返回，效果一样，能少一次出队操作。第二，g[nx][ny] == '#'这个判断必须放在越界判断之后，否则就可能在非法下标上读内存，虽然大多数情况下不会崩，但这是明显的安全隐患。

4.3 参数选择与复杂度的实际感受

理论复杂度是 O(n×m)，每个格子最多入队一次、出队一次，每次出队扫四个方向，所以总操作数大约是 4×n×m 加上常数。以 n=m=1000 为例，总共约 400 万次内层循环，每次循环里有几个判断和一次可能的入队，实测在普通机器上跑完大概几十毫秒，完全够用。

但“够用”的前提是常数没被放大。如果队列里存的是结构体而不是pair，如果每次入队都拷贝一个大对象，如果dist数组用vector<vector<int>>而不是静态数组，常数可能翻好几倍。我给个经验值：当 n×m 超过 10^6 时，把队列元素类型控制在 8 字节以内（比如把坐标压成一个整数x * (m+1) + y），把数组开成全局静态数组而不是在函数里动态分配，这两条能省下相当可观的时间。

5. 变形与延伸：题目改一版，模板要动哪几刀

5.1 常见变体对照表

同一道“旅游”题，出题人稍微改一改条件，BFS 的写法就得跟着调整。我把遇到过的高频变体整理成一张表，做题的时候可以先对着表定位，再决定改哪里。

拿“带钥匙”这个变体举个例子。假设地图上有若干把钥匙和对应的门，钥匙可以用一个二进制位表示，那么状态就是dist[x][y][mask]，其中 mask 是当前手上钥匙的集合。转移的时候，如果新格子是钥匙，mask 就或上对应的位；如果新格子是门，只有 mask 里对应的位是 1 才能通过。这种题的状态数直接乘以 2^k，k 是钥匙种类数，通常 k ≤ 10，所以总状态数可控。

5.2 边权不为 1 时的三条路

前面提过，边权不全为 1 是 BFS 的硬伤。这里展开说三条路线的取舍。

第一条路是拆点，也就是把一个代价为 k 的格子拆成 k 个串联的中间节点，中间节点之间用代价 1 的边连接，整体边权就拉回 1 了。这条路的最大优势是代码改动极小，主循环一行不用动，只需要在扩展时多加一层“进入代价格要连续走 k 步”的判断。缺点也很明显：如果 k 很大，拆出来的节点数会膨胀，搜索空间跟着变大。所以这条路适合 k ≤ 3 这种小代价。

第二条路是 0-1 BFS，用双端队列代替普通队列。核心思想是：遇到代价为 0 的边，就把新节点塞到队头，让它优先被扩展到；遇到代价为 1 的边，就塞到队尾。这样队列里的元素天然按距离单调不减排列，取出来的永远是最小的。代码实现如下：

deque<pair<int,int> > dq; memset(dist, 0x3f, sizeof(dist)); dist[sx][sy] = 0; dq.push_front(make_pair(sx, sy)); while (!dq.empty()) { int x = dq.front().first, y = dq.front().second; dq.pop_front(); for (int d = 0; d < 4; ++d) { int nx = x + dx[d], ny = y + dy[d]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (g[nx][ny] == '#') continue; int w = cost(nx, ny); // 进入该格子的代价，0 或 1 if (dist[x][y] + w < dist[nx][ny]) { dist[nx][ny] = dist[x][y] + w; if (w == 0) dq.push_front(make_pair(nx, ny)); else dq.push_back(make_pair(nx, ny)); } } }

注意这里的vis判定方式变了，不能简单地用“访问过就跳过”，而要用“能不能更新更短距离”。这一点和普通 BFS 差异很大，改的时候别照抄模板。

第三条路是直接上 Dijkstra，用优先队列维护。适用面最广，任何正整数边权都能处理，代价是常数大、代码长。我的判断标准很简单：如果边权种类只有两种且其中一种是 0，用 0-1 BFS；其他情况一律 Dijkstra，不去纠结那点常数。

5.3 多源 BFS 与反向 BFS

有两个小技巧特别实用，但很多模板里没提。

多源 BFS是指有多个起点，要求每个格子到最近起点的距离。做法简单到有点反直觉：把所有起点一次性全部入队，距离全部初始化为 0，然后照常跑 BFS。正确性在于，BFS 的队列本来就是按距离排序的，所有距离为 0 的点排在前面，扩展出来的距离为 1 的点自然也是全局最近的。

反向 BFS是指从终点往起点搜。在无权图里正向反向结果一样，看起来没什么用，但在两类场景下是救命稻草：一是终点只有一个而起点有很多（或者起点是一个集合），反向搜只需一次 BFS；二是需要统计“哪些点能到达终点”时，正向搜要跑很多次，反向搜一次就够。

5.4 路径还原：怎么把走过的路记录下来

有些题目不只问最短距离，还要输出具体走法。做法是额外开一个数组记录每个格子的前驱方向，比如from[x][y]存的是“从哪个方向走到 (x, y) 的”。BFS 结束后从终点开始，按前驱方向一步步往回退，退到起点为止，把路径上的坐标收集起来再反转，就得到完整路径。

这里有个细节：如果存在多条最短路径，题目可能要求输出字典序最小的那条。这时候方向数组的顺序就变得至关重要，必须按题目规定的优先级排列方向，比如“上、左、右、下”这种顺序，因为 BFS 的扩展顺序直接决定了哪条路径先被记录。我在这上面栽过一回，方向数组随手按上下左右写，结果要求“字典序最小”的那组数据全错。

6. 调试实录：那些提交后 WA 和 TLE 的夜晚

6.1 高频错误速查表

下面这些错误我几乎全犯过，整理出来当检查清单用，交题之前挨个对一遍，能省不少重交次数。

其中“标记放在出队时”这一条最能迷惑人。因为它在小数据上完全正确，样例也能过，只有数据规模上去之后才会以 TLE 或 MLE 的形式暴露出来。我当时的排查方式是：在程序里加一个计数器，统计队列曾经达到的最大长度，结果发现它比格子总数大了一个数量级，这才意识到问题所在。

6.2 手造数据与对拍

当样例全过但提交不过的时候，最快找出问题的方式是对拍。具体做法是：写一份暴力解法（比如 DFS 加剪枝，或者干脆枚举所有路径），再写一个随机数据生成器，让两份程序跑同一组数据，比较输出。

随机数据生成器要覆盖几种边界：地图最小（1×1、1×2）、起点就在终点、终点被完全围死、整张图没有障碍、整张图全是障碍只剩下一条羊肠小道。我一般会把这些极端情况单独写死几组，再配合随机生成，覆盖率就差不多了。

对拍脚本写起来也不复杂，用 shell 循环几百次，每次生成数据、跑两份程序、比较输出，一旦不同就停下来保留数据。这套流程我用了好几年，几乎所有难调的搜索题都是靠它定位的。

注意：对拍之前先确认暴力程序本身是对的，否则两份都错、结果一致，反而会让你误以为程序没问题。

6.3 关于输入输出的几个小陷阱

有几个坑和算法无关，纯属工程细节。

第一，多组数据的情况。有些题会连续给好几组数据，每组都要重新初始化数组。如果vis或者dist忘了清空，第二组数据的答案就会莫名其妙地偏小。稳妥做法是把初始化写在读入之后，或者用一个“时间戳”技巧：数组里存的是上次访问的组号，判断时比较组号是否等于当前组，省去每次memset的开销。

第二，输出格式。有的题要求行末不能有多余空格，有的题要求每组数据之间空一行，这些格式问题经常导致“答案完全正确却判错”。交题之前把输出语句再核对一遍，比调试算法省事多了。

第三，字符读入的坑。scanf("%c")会把换行符也读进来，导致地图错位；用scanf("%s")就没这个问题。如果一定要逐字符读，记得在读之前把空白字符吃掉。

6.4 我个人的几条实操体会

第一，先把状态定义写在纸上再写代码。我现在遇到任何搜索题，都会先在草稿纸上写一行“状态 = (x, y, 附加维度)”，然后估算状态数，最后才动手。这个习惯让我少写了无数份白写的代码。

第二，不要迷信模板。模板能帮你省下打字时间，但它不会帮你判断这道题该不该用双端队列、该不该多开一维。真正决定成败的是建模那一步，代码只是把建模翻译出来而已。

第三，测数据要测“丑”的。漂亮的数据测不出问题，随机生成的地图往往一片开阔、四通八达，恰好避开了所有边界情况。自己造几条全是死路的、起点被围住的、终点在角落的，往往一测就现原形。

第四，时间允许的话，把复杂度算清楚再交。我见过太多人因为“感觉能过”就交了，结果 TLE 之后反复优化常数，其实只要换个算法就能过。花两分钟算一下状态数和操作数，比优化半小时常数划算得多。

这类题目做多了，你会发现真正变化的只有“状态怎么定义”和“边权是不是 1”这两件事，剩下的队列、标记、距离递推，几乎是肌肉记忆。把模板吃透、把状态设计想清楚，剩下的就是熟练度问题。