企业官网建设流程全解析

1. 先把故事外壳剥掉：这道题的内核是无权网格图上的最短路

“BFS 写旅游题”这个说法听着有点绕，但凡是刷过网格地图类搜索题的人，看到标题里那三个字母，心里基本就有数了——这活儿的本质就是在无权图上求最短路径。这道来自某题库 1996 号的题目，题干被包装成小 W 出门旅游、在景区地图上找路线，可一旦把“景区”“游客”“景点”这些词换成“节点”“源点”“目标点”，剩下的骨架和模板题没有任何区别。

我先把话说明白：原题面我这里拿不到完整版本，下面按这类“旅游”命名题最常见的形态来展开——一个 n 行 m 列的字符网格，#表示走不过去的山体或水域，.表示可通行的平地，S是入口，T是出口，每次只能上下左右走一格，每格耗时 1，问从入口到出口最少要走几步，走不到输出 -1。这是绝大多数同名题的标准设定，如果你手上的题面在细节上有出入（比如加了步数上限、加了多个景点、加了补给点），第 4 章专门讲这些变种怎么接，思路是通用的。

这篇文章适合谁看？如果你刚学完 BFS 的理论、只会背模板但一遇到具体题目就不知道怎么下手，那这篇正好；如果你已经能独立写出 BFS，但总在细节上翻车——数组越界、读入读到换行、多组数据不清空、队列开到爆内存——那第 3 章和第 5 章值得你重点看，那些坑我一个个踩过。

核心关键词先摆出来：BFS、广度优先搜索、最短路径、网格图、队列、访问标记、多源扩展、0-1 BFS。整篇文章围绕这几个点转，不跑偏。

2. 为什么这题非 BFS 不可：三类搜索的适用边界

2.1 从“每步代价相同”推出 BFS 的合法性

选算法之前先问一个问题：这张图上每条边的“代价”是不是一样？这道题里答案很明确——不管你是从 (1,1) 走到 (1,2)，还是从 (100,100) 走到 (100,101)，都只花一步，代价恒等于 1。这个前提太重要了，它直接决定了 BFS 能用。

BFS 的正确性来自一个不变量：队列里节点的距离值单调不减。因为每扩展一层，距离就加 1，所以队列天然是按距离从小到大排好的。这就意味着，任何节点第一次被访问到时，它拿到的距离一定就是最短距离，后面不可能再出现更短的走法。我常跟人打这个比方：往平静的水面扔一颗石子，涟漪一圈一圈往外扩，第一圈到达的岸边肯定是最先被波及的，不存在“第二圈比第一圈先到”的情况。BFS 就是这个涟漪。

理解了这一点，后面很多写法上的取舍就顺理成章了，比如“为什么入队的时候就要打标记”这个问题，本质就是在维护这个不变量。

2.2 DFS 为什么不行，Dijkstra 为什么是杀鸡用牛刀

有人可能会想，DFS 也能遍历全图啊，为什么不用它？因为 DFS 是“一条道走到黑”，它找到的第一条路径完全可能是绕了远路的那种。要想用 DFS 求最短路，你得把所有路径都枚举一遍再取最小值，复杂度直接爆炸，指数级起步，稍微大点的图就跑不动了。DFS 适合的是“是否存在一条路径”“连通块计数”“拓扑排序”这类问题，求最短路不是它的主场。

那 Dijkstra 呢？Dijkstra 当然能解，而且结果一定对。但它是为带权图设计的，需要堆来维护当前最小距离，复杂度是 O(E log V)。这道题所有边权都是 1，用 Dijkstra 相当于拿高射炮打蚊子——结果没错，但白白多背一个 log，代码还长一截。什么时候必须请出 Dijkstra？当题目里出现了不同的移动代价，比如平地上走一步花 1、爬山花 3、坐缆车花 0，这时候 BFS 的“等层扩展”就不成立了，Dijkstra 或者 0-1 BFS 才管用。这个判断标准我建议记牢：边权全为 1 用 BFS，边权只有 0 和 1 用双端队列 0-1 BFS，边权任意非负用 Dijkstra。

2.3 数据规模反推：为什么 O(nm) 是道生死线

竞赛题给出的数据范围往往就是在暗示算法。这类网格题常见的是 n, m ≤ 1000，也就是说总格子数最多一百万。BFS 的复杂度是 O(nm)，因为每个格子最多入队一次、出队一次，每次出队检查四个方向，总操作数大约是 4nm，一百万的四倍就是四百万次基本操作，跑进 1 秒绰绰有余。

反过来看，如果这题允许四个方向走且边权不等，那最坏得用 Dijkstra，复杂度变成 O(nm log(nm))，一百万乘以 20，两千万次操作，虽然还能过，但常数已经吃紧了。再往上，如果 n, m 到 2000，四百万个格子，Dijkstra 基本就没戏了。你在读题的时候如果看到数据范围在 10^6 这个量级，脑子里第一反应就该是“线性或近线性算法”，BFS 正好卡在这个位置上。

注意：判断能不能用 BFS，先看边权是否统一，再看数据规模是否允许 O(nm)。这两个条件缺一不可，很多人只看了第一个就动手，结果数据范围一大，代码里常数没优化好，卡在最后几个点。

3. 核心设计：状态、距离数组和队列怎么配

3.1 状态表示：一个格子就是一个状态，什么时候才需要加维度

状态定义是整个搜索的地基。这道题的状态非常朴素——坐标 (x, y) 就是状态，不需要额外维度。因为在这个模型里，你站在哪个格子上，能做的事完全一样，与你怎么走到这里的、走了多少步都无关。这种“无后效性”是 BFS 能用一个二维数组存距离的前提。

但有些题就必须加维度了。举个例子：如果景区里散布着若干把钥匙，你必须先拿到钥匙才能通过某道门，那状态就得从 (x, y) 升级成 (x, y, 已收集的钥匙集合)，用二进制状态压缩存钥匙。再比如题目限制“每个格子只能经过一次”，那状态还得再带上访问历史，规模直接爆炸，这时候往往就得换思路了。

我总结的判断方法是：问自己“两个不同的到达方式，会不会影响接下来的决策”。如果不会，二维就够；如果会，就得把那个“影响决策的因素”塞进状态里。这道题显然不会，所以老老实实用二维数组。

3.2 距离数组和标记数组：能不能合成一个

新手常见的写法是开两个数组，一个visited存能不能到，一个dis存步数。能跑，但没必要。更省事的做法是把两者合一：用一个dis数组，初始值全设成 -1，-1 表示没访问过，非负表示最短距离。这样判断“是否访问过”就变成判断dis[nx][ny] == -1，一行搞定，还省了一半内存。

这里有个细节值得掰开说。memset(dis, -1, sizeof(dis))之所以能把 int 数组全部置为 -1，是因为 -1 的补码是 0xFFFFFFFF，每个字节都是 0xFF，memset 按字节填充正好填出这个值。如果你想把数组置成 1，就没这么好运气了，memset 按字节填只能得到 0x01010101，也就是 16843009，不是 1。这个坑必须记住：memset 只适合置 0、-1 和 0x3f 这类所有字节相同的值。想初始化成其他数，老老实实写循环。

另一种常见写法是用0x3f3f3f3f表示无穷大，好处是两两相加不会溢出 int，方便做松弛操作。但这题用不上松弛，-1 更直观，我倾向于用 -1。

3.3 队列：STL 容器还是手写数组，该怎么选

队列这块有两套写法，各有各的道理。

用 STL 的queue<pair<int,int>>写起来最省心，不用管容量，不用管头尾指针，push 和 pop 语义清晰。缺点是有额外的封装开销，每次 push 都要在底层容器上做一次操作，节点数上百万的时候，累积起来的常数损耗不算小。我做过粗略对比，同样的逻辑，手写数组队列在百万级节点规模下通常能快上一截，具体差多少跟编译器、标准库实现都有关系，但方向是确定的。

手写队列的关键是容量要开对。上界很好推：每个格子最多入队一次，所以队列长度不可能超过 n × m。给数组开n * m的大小就绝对安全，不需要多开，因为同一时刻队列里的元素绝不会超过总状态数。但如果你的状态加了维度，比如变成 (x, y, 状态)，那上界就要乘以状态的种类数，这个一定要算清楚。

// 手写队列，容量严格按最大可能状态数开 const int MAXN = 1005; int qx[MAXN * MAXN], qy[MAXN * MAXN]; int head = 0, tail = 0; // 区间为 [head, tail) qx[tail] = sx; qy[tail] = sy; tail++; // 出队：取 qx[head], qy[head]，然后 head++ // 入队：qx[tail] = x; qy[tail] = y; tail++

用左闭右开的[head, tail)区间，判断队空就是head == tail，比用head <= tail少很多心智负担。这个习惯我从一开始就养成了，后来写所有需要手写队列的题都没再因为这个出过错。

提示：队列容量按“最大状态数 × 每状态入队次数”计算。如果实现正确（入队即标记），每状态只会入队一次；如果没有及时标记，同一状态可能反复入队，这时候固定容量的数组就会溢出，表现为莫名其妙的运行时错误或者答案错乱。

4. 动手实现：从读入到输出，一步步写扎实

4.1 读入环节：字符网格最容易翻车的地方

我能负责任地说，网格题里一半以上的“莫名其妙 WA”都出在读入上。坑在哪？

第一个坑是换行符。如果你用scanf("%c", &c)或者cin >> c一个一个字符读，行末的\n（有些环境下还有\r）会被当成一个有效字符读进来，于是你的网格整体错位一格，边界判断全乱。这个 bug 极其隐蔽，因为程序不会崩，只是答案不对，而且小数据有时候还能碰巧对。

第二个坑是行末残留。如果某一行读了 n 个字符，但实际这行有 n+1 个字符（多一个换行），下一行读的时候就会先读到换行。这种情况用getchar()手动吞掉换行可以解决，但代码里很容易漏掉某处。

我的标准做法是：字符串整行读，下标从 1 开始。

for (int i = 1; i <= n; ++i) { scanf("%s", g[i] + 1); // 从第 1 列开始存，g[i][0] 空着 }

%s会自动跳过前导空白（包括换行），读到下一个空白为止，所以完全不用担心换行污染。g[i] + 1这个写法让字符串从下标 1 开始写，第 0 列空出来，好处是边界判断可以直接写x < 1 || x > n，不用处理 -1 下标，省心很多。

下标从 0 开始当然也行，但那样边界判断就得写x < 0 || x >= n，而且dis[x-1][y]这种写法在 x=0 时就是负下标，容易出错。从 1 开始是我在网格题上最推荐的习惯，多浪费一行一列的内存，换来的是少一堆越界 bug。

4.2 方向数组和边界判断：顺序不能反

方向数组是网格题标配：

const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; // 上、下、左、右

写的时候注意 dx 和 dy 要配对，上对应 (-1, 0)，下对应 (1, 0)，左对应 (0, -1)，右对应 (0, 1)。我见过有人写成dx = {0, 0, -1, 1}、dy = {-1, 1, 0, 0}，逻辑上其实也对，只是方向顺序变了，但如果配错对——比如把 (-1, 0) 和 (0, -1) 搞混——就会出现“走斜线”的诡异现象，答案偏差很大。

更关键的是边界判断必须在访问数组之前：

int nx = x + dx[d], ny = y + dy[d]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 先判越界 if (g[nx][ny] == '#') continue; // 再判障碍 if (dis[nx][ny] != -1) continue; // 最后判是否访问过 dis[nx][ny] = dis[x][y] + 1; qx[tail] = nx; qy[tail] = ny; tail++; // 入队

这个顺序反了就是未定义行为。如果你先写if (dis[nx][ny] != -1)，而 nx 是 -1 或者 n+1，那就是在访问数组外面的内存，读到的可能是任意值。轻则答案错，重则在某些环境下直接崩溃。这个顺序我是当成肌肉记忆来练的，写完先扫一眼这三行的顺序对不对。

4.3 完整代码与逐段拆解

下面这版是基础版的完整实现，求 S 到 T 的最少步数，走不到输出 -1：

#include <cstdio> #include <cstring> const int MAXN = 1005; int n, m, sx, sy, tx, ty; char g[MAXN][MAXN]; int dis[MAXN][MAXN]; int qx[MAXN * MAXN], qy[MAXN * MAXN]; const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; int bfs() { memset(dis, -1, sizeof(dis)); // -1 表示未访问 int head = 0, tail = 0; dis[sx][sy] = 0; qx[tail] = sx; qy[tail] = sy; tail++; while (head < tail) { int x = qx[head], y = qy[head]; head++; if (x == tx && y == ty) return dis[x][y]; // 提前返回 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; if (dis[nx][ny] != -1) continue; dis[nx][ny] = dis[x][y] + 1; qx[tail] = nx; qy[tail] = ny; tail++; } } return -1; // 队列空了还没碰到终点，说明不连通 } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%s", g[i] + 1); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { if (g[i][j] == 'S') { sx = i; sy = j; } if (g[i][j] == 'T') { tx = i; ty = j; } } printf("%d\n", bfs()); return 0; }

几个值得单独拎出来说的点。

第一，起点入队时立刻置 dis 为 0。这一步如果忘了，起点会被当成未访问，它自己可能被邻居重新入队一次，虽然结果大概率还是对的（因为撞到dis != -1就跳过了），但如果起点周围有环，可能出现距离值被覆盖的情况。更重要的是，忘了这一步说明你没想清楚“dis 数组承担了双重职责”这件事。

第二，提前返回放在出队时而不是入队时。理论上入队时判断也能提前返回，而且能省一点队列操作，但要注意入队时的 dis 值也是正确的（因为入队时就赋好了值）。两种写法都对，我习惯放在出队，因为此时这个节点的距离一定已经是最小的，语义上更严谨，也避免“终点就是起点”这种边界情况的特殊处理。

第三，主函数里那次全图扫描别忘了。如果某个格子既是 S 又是 T（题目数据可能这么恶心），或者根本没找到 S，那 sx、sy 就是全局变量默认的 0，起点跑到 (0,0) 去了，全盘皆错。稳妥的做法是初始化时把 sx 设成一个不可能的值，找到后再用，找不到就特判。

4.4 内存和常数：把限制算明白再写

很多题目的内存限制是 64MB 或者 128MB，网格题特别容易爆。我们来算笔账。

假设 n = m = 1000，格子总数 10^6。

• char g[1005][1005]：约 1MB
• int dis[1005][1005]：约 4MB
• qx[1000*1000] + qy[1000*1000]，都是 int：约 8MB

加起来 13MB，没问题。但如果你的 dis 用int，队列又用queue<pair<int,int>>（每对 8 字节，还要加上 deque 的块状分配开销），内存会往上飘，实际占用通常比理论值多出不少。

如果 n, m 涨到 2000，格子数变成 4×10^6：

• dis就是 16MB
• 两个 int 队列就是 32MB
• 合计超过 50MB

这时候就危险了。解决办法有两个：一是把 dis 换成short（距离最大不超过 4×10^6，short 装不下，但如果数据保证答案不大就够用，需要谨慎评估）；二是把二维坐标压成一维编码id = x * m + y，队列只存 int，容量减半。第二种更通用，我一般不嫌麻烦就直接用一维编码，反正解码也就两行。

常数方面还有个小技巧：把dis[x][y]先取出来存到局部变量int d0 = dis[x][y];，循环里用d0 + 1。因为dis[x][y]在四方向循环里被反复读取，编译器不一定能把它提到循环外（涉及内存别名分析），手动提出来能少几次访存。这个优化在百万级数据上能看出一点差别，但别指望有数量级的提升。

5. 题目变形：三种常见追问怎么接

5.1 加一个步数上限：提前终止和剪枝的位置

最常见的变形是：小 W 只有 K 点体力，每走一步消耗 1 点，问他最多能游览多少个不同的格子（或者能不能到达终点）。这本质上就是限制最大扩展层数。

最简单的改法是在出队时判断：

while (head < tail) { int x = qx[head], y = qy[head]; head++; if (dis[x][y] == K) continue; // 已经走满 K 步，不再往外扩 for (int d = 0; d < 4; ++d) { // ... 正常扩展 } }

这个剪枝为什么对？因为 BFS 是按层扩展的，队列里的 dis 单调不减，一旦某个节点的 dis 达到 K，它后面所有节点的 dis 都 ≥ K，都不可能再往外扩展了。所以直接continue掉，省下四方向的检查。

注意这里写== K而不是>= K。因为正常情况下 dis 不会超过 K（超了就不会被入队），写>=也没错，但==更能表达意图。我更推荐在扩展时做限制，也就是判断if (dis[x][y] + 1 > K) continue;，这样从源头上就不会有超限节点入队，队列更干净。

如果要统计“K 步内能到达的格子数”，在 BFS 结束后扫一遍 dis 数组，统计有多少个位置的值在[0, K]区间内就行。这一步别忘了把起点算进去（dis 为 0 的那个），我见过有人统计时漏掉起点，差 1 分。

还有个容易忽略的点：如果 K 已经大于等于网格的直径，那整个连通块都能走到，此时 BFS 会遍历完所有可达格子，复杂度还是 O(nm)，不会因为 K 大而变慢。这个性质让剪枝显得很安全。

5.2 加多个起点：多源 BFS 的初始化只需改一行

另一种变形是：景区有多个入口，小 W 可以从任意一个入口进，问到达某个景点的最短距离。这就是多源最短路。

关键洞察是：多源 BFS 等价于“加一个超级源点，超级源点到所有起点的距离都是 0”。所以实现上，你只需要把所有起点在初始化时全部入队，dis 全部设为 0，剩下的一行都不用改。

memset(dis, -1, sizeof(dis)); int head = 0, tail = 0; for (int i = 0; i < (int)starts.size(); ++i) { int x = starts[i].first, y = starts[i].second; dis[x][y] = 0; qx[tail] = x; qy[tail] = y; tail++; } // 后面完全一样

为什么这样是对的？直觉上，把多个石子同时扔进水里，涟漪从多个中心同时往外扩，某个位置最先被哪圈涟漪扫到，它的距离就是到最近源点的距离。严格证明还是靠那个不变量：队列里的距离单调不减，任何节点第一次被访问时拿到的就是最小值。

这里有个坑：如果多个起点有重复，或者某个起点是障碍，直接入队会导致错误。入队前必须做一次合法性检查，把不合法的起点过滤掉。我就吃过这个亏，题目数据里给了一个障碍点作为起点，结果程序直接从这个障碍点往外扩展，答案偏小。

还有一个进阶版本：如果起点本身有“代价”（比如从不同的门进要买不同价格的票），那就不能用简单多源 BFS 了，得改成带初始距离的优先队列，本质退化成 Dijkstra。

5.3 加补给点和传送门：BFS 什么时候就不够用了

这是最能体现思维深度的一类变形。假设景区里散布着补给站，走到补给站体力回满。这时候还能用 BFS 吗？

如果每个补给站只用一次（即回满后不会重复触发），其实还能做。因为 BFS 保证第一次到达补给站时距离最短，而“越早到达补给站越好”是成立的——你到得越早，剩余体力越多，后续能走的范围越大。所以可以在 BFS 里加一个状态维度表示“当前体力”，或者用分段 BFS 的方式处理。

但如果补给可以反复触发，或者传送门能双向跳，问题立刻复杂起来。传送门的边权是 0（跳过去不花时间）或者 1，普通移动边权是 1，这时候图里出现了 0 权和 1 权混合的情况，普通 BFS 就失效了。正确的工具是双端队列 BFS（0-1 BFS）：遇到边权为 0 的转移，把新节点 push 到队首；边权为 1 的转移，push 到队尾。这样队列里依然能保持距离单调，复杂度还是 O(V + E)。

// 0-1 BFS 的核心：按边权决定插队首还是队尾 if (w == 0) dq.push_front(nv); else dq.push_back(nv);

再复杂一点，如果传送门有使用次数限制、或者移动代价是任意正整数（比如爬坡花 3 点体力、平路花 1 点），那就只能上 Dijkstra 加优先队列了。判断标准还是那句老话：看边权。边权全是 1 用 BFS，0/1 混合用双端队列，任意非负用堆。

我在实际做题时养成了一个习惯：读完题先在纸上写下“状态是什么、转移是什么、每条转移的代价是多少”，这三行写清楚了，用哪个算法是水到渠成的事，根本不用纠结。

6. 常见问题与排查实录

6.1 五种看起来没毛病的 WA

第一种：入队时不标记，出队时才标记。这是最经典的性能陷阱。如果你在出队时才把 visited 置真，那么同一个节点在被访问之前，可能被它的多个邻居分别入队一次，队列里堆满重复元素。在网格图上，一个格子最多有 4 个邻居，最坏情况队列长度会膨胀好几倍，虽然答案通常还是对的（因为第一次出队的就是最短的），但复杂度和内存都退化了。正确做法是入队时立刻标记。

第二种：距离数组没初始化。全局数组默认是 0，如果你的 dis 用 0 表示“未访问”，那起点之外的所有格子一开始就被认为“已访问且距离为 0”，BFS 一步都走不动。所以要么用 -1 区分，要么老老实实 memset 成无穷大。这个 bug 在本地跑小数据时可能因为内存恰好是干净的而通过，一交上去就 WA，特别坑。

第三种：多组数据没清空。有些题目一个测试文件里有多组数据，每组都要重新 memset。如果你只 memset 了 dis，忘了清空 head/tail，或者忘了重置 sx/sy，第二组数据直接错乱。我的做法是把所有全局状态的初始化封装成一个init()函数，主循环里每组数据开头调一次，绝不错漏。

第四种：边界判断写成了>=。if (nx < 1 || nx >= n)少了一个，第 n 行永远走不到。这种 bug 单步调试很容易发现，但如果只靠肉眼看代码，有时候真会漏。

第五种：把字符 '1' 当成数字 1。有些题目的网格里是数字字符表示代价，很多人直接从g[nx][ny]里拿值参与运算，忘了减 '0'。结果代价全部偏大 48，答案离谱。

6.2 问题速查表

6.3 调试三板斧：打印、手推、对拍

第一板斧是打印距离矩阵。BFS 跑完后把 dis 按网格格式打出来，用 -1 表示不可达。这一步极其有效，因为 BFS 的距离场会呈现非常规律的“同心圆”形状，一旦你看到某个本该是 2 的位置变成了 5，或者出现了一片莫名其妙的 -1，问题出在哪个方向立刻就能定位。我基本上每道搜索题都会写这么一段调试代码，用完注释掉，从不嫌麻烦。

第二板斧是手推小数据。构造一个 3×3 或者 4×4 的小网格，自己用笔在纸上走一遍，记下每个格子的最少步数，然后跟程序输出逐个比对。第一个对不上的格子，就是 bug 的藏身之处。这个方法比盯着代码看效率高十倍。

第三板斧是对拍。写一个暴力版本（比如 DFS 枚举所有路径取最小，只在小数据上跑），再写一个数据生成器，随机生成几百组小规模输入，两个程序对比输出。一旦发现不一致，把那份输入单独存下来分析。对拍能抓到那些你自己想不到的边界情况，是赛前必备的手段。

注意：写对拍的时候，暴力版本一定要写对，否则会出现“两个都错但错得一样”或者“暴力错了反而显得正解错”的尴尬局面。暴力版本要尽量朴素，不要做任何优化，宁可慢也要保证逻辑正确。

6.4 几个我从实战里攒下来的小技巧

技巧一：把方向循环展开。如果追求极致常数，可以不用 for 循环走方向数组，而是写四段重复代码。这样能省掉循环控制开销和数组下标计算，编译器也更容易优化。不过我一般只在时限特别紧的时候才这么干，因为代码会变丑、变长，容易抄错。

技巧二：用int存坐标而不是pair。手写队列时，两个 int 数组比queue<pair<int,int>>省内存也省时间，因为 pair 会有对齐填充，实际占用可能比 8 字节还多。如果进一步压成一维编码id = x * (m + 1) + y，队列只要一个 int 数组，内存直接减半。

技巧三：先判断终点再扩展。很多题目终点可能在图的很深处，提前判断能省下大量无用的扩展。但要注意，判断必须放在出队之后、扩展之前，这样保证取到的距离是最小的。

技巧四：读入用%s而不是逐字符。前面说过，%s自动跳过空白，不会受换行干扰。但要注意%s会在字符串末尾补\0，所以你的数组每行至少要开 m + 2 的大小，从下标 1 开始写正好给\0留了位置。

技巧五：下笔前先把变量命名想清楚。sx, sy起点，tx, ty终点，nx, ny邻居，qx, qy队列。这套命名我用了很多年，读代码时眼睛一扫就知道是什么，不用反复回翻定义。别小看这个，比赛时改 bug 的速度很大程度上取决于代码的可读性。

7. 我个人在这类题上的几点体会

写了这么多版 BFS，我最大的感受是：模板本身几分钟就能背下来，真正耗时间的是那些边角情况。同一个模板，换个读入方式、换个边界判断顺序、换个标记时机，正确性和效率就完全不同。所以别急着追求“写得快”，先把每一行为什么这么写搞清楚。等你把“为什么入队就要标记”“为什么越界判断要在最前面”“为什么提前返回要放在出队时”这三个问题都能不假思索地答出来，这道题以及它背后的一整类网格搜索题，基本就吃透了。

另外还有个习惯我想分享：每次写完 BFS，我都会刻意造一组“起点就在终点旁边”“起点被障碍包围”“整个图只有起点”这样的小数据跑一遍。这些极端情况往往就是评测数据里的坑点，提前自己踩一遍，比交上去等反馈要划算得多。踩过的坑越早越好，因为同样的坑你不会踩第二次。