企业官网建设流程全解析

1. 从标题拆解这道题到底在考什么

看到"G - Borg Maze （Prim&BFS）"这个标题，第一反应是这应该是一道算法竞赛题，题号G，题目名Borg Maze，括号里标注了Prim和BFS两个算法关键词。这种标注方式在竞赛题解社区里很常见，相当于出题人或者题解作者直接告诉你：这道题的核心解法就是最小生成树（Prim算法）加广度优先搜索（BFS）。

那为什么一道题要同时用到这两个算法？它们各自负责什么？这是理解整道题的关键。简单来说，BFS负责在迷宫网格上算出各个关键点之间的最短距离，Prim负责把这些关键点用最小的总代价连通起来。一个管"距离计算"，一个管"连通优化"，两者配合才能得到最终答案。

这道题适合谁看？如果你正在刷图论专题、准备算法竞赛、或者对最小生成树和BFS的组合应用感兴趣，那这道题是一个非常好的练习素材。它不像纯模板题那样直接套板子就行，而是需要你先做一层建模转化——把迷宫问题转化成图论问题，再用两个经典算法串联求解。这个转化过程才是真正锻炼思维的地方。

我见过不少人做这道题时，BFS部分写得没问题，Prim也没问题，但就是在建模这一步卡住了，不知道怎么把迷宫里的外星人坐标变成图的节点。所以这篇博文我会从建模思路开始讲，把每一步的"为什么"都说清楚，然后给出可以直接参考的代码实现，最后分享一些我在做这类题时踩过的坑和排查技巧。

2. 题目建模与核心思路拆解

2.1 迷宫问题的本质转化

题目的大致场景是这样的：给你一个迷宫，迷宫里有若干外星人（用字母A表示）和若干分裂点（用字母S表示），迷宫中有墙壁（用#表示）和通道（用空格表示）。你需要找到一种方式，把所有外星人连通起来，使得总的连接代价最小。每走一步的代价是1。

这个描述一出来，有经验的人马上就能反应过来：这是一个最小生成树问题。把每个外星人（包括起始分裂点S）看作图中的一个节点，节点之间的边权就是它们在迷宫中互相到达的最短距离。求出这个完全图的最小生成树，其总边权就是答案。

但问题在于，你不可能手动去算每两个外星人之间的最短距离。迷宫里可能有几十个外星人，两两组合就是上千对。这时候BFS就派上用场了——对每个关键点跑一次BFS，就能算出它到其他所有关键点的最短距离。

所以整个流程分为两大阶段：

• 第一阶段：扫描迷宫，收集所有关键点（S和A）的坐标，给它们编号
• 第二阶段：对每个关键点跑BFS，构建邻接矩阵（或边列表）
• 第三阶段：在邻接矩阵上跑Prim算法，求最小生成树的总权值

这个思路非常清晰，但魔鬼在细节里。下面我逐个拆解每个阶段的关键决策。

2.2 为什么选Prim而不是Kruskal

括号里明确写了Prim，那为什么不用Kruskal？这其实和图的稠密程度有关。

假设迷宫里有n个关键点，那我们构建出来的图是一个完全图——因为任意两个关键点之间都可能存在通路（只要迷宫是连通的）。完全图的边数是n*(n-1)/2。如果n=100，边数就是4950条。这个规模下，Prim和Kruskal都能跑，差别不大。

但关键在于，我们已经有邻接矩阵了。BFS跑完之后，距离信息天然存储在一个二维矩阵里，直接用Prim的邻接矩阵版本是最自然的——O(n^2)的时间复杂度，不需要额外维护并查集，也不需要对所有边排序。代码写起来更直接，出错概率更低。

Kruskal需要把所有的边提取出来排序，虽然在这个规模下也没问题，但多了一步操作就多一个出错的机会。而且竞赛中时间宝贵，能用最直接的方案就用最直接的。

注意：如果关键点数量特别大（比如超过1000个），那O(n^2)的Prim可能就吃不消了，这时候需要考虑其他优化。但一般这类迷宫题的规模不会那么大，n通常在100以内。

2.3 BFS的角色与实现要点

BFS在这道题里的任务很单一：给定一个起点，算出它到迷宫上所有可达格子的最短步数。然后我们只关心那些是关键点的格子，把它们的距离记录下来。

BFS的实现有几个容易出问题的地方：

第一，方向数组。迷宫问题通常是四方向移动（上下左右），方向数组写成dx[]={-1,1,0,0}和dy[]={0,0,-1,1}。这个没什么好说的，但要注意边界检查。

第二，访问标记。BFS必须标记已访问的格子，否则会死循环。可以用一个二维布尔数组，也可以直接在距离数组上初始化-1，检查是否为-1来判断是否访问过。后者更简洁，推荐使用。

第三，队列的使用。C++里用queue<pair<int,int>>或者手写数组模拟队列都行。如果追求速度，手写数组队列比STL的queue快不少，因为避免了动态内存分配。竞赛中如果时间卡得紧，建议手写。

第四，距离的初始化。每次BFS之前，距离数组都要重置为-1。如果关键点有n个，就要跑n次BFS，每次都要重置整个距离数组。这个重置操作看起来不起眼，但如果迷宫很大、关键点很多，重置的开销也会累积。可以用memset或者fill来快速重置。

2.4 邻接矩阵的构建逻辑

BFS跑完之后，我们得到的是每个关键点到迷宫上每个格子的距离。但我们只需要关键点之间的距离。所以对于第i个关键点，跑完BFS后，遍历所有关键点j，如果dist[keyPoint[j].x][keyPoint[j].y] != -1，那adj[i][j] = dist[keyPoint[j].x][keyPoint[j].y]。

这里有一个隐含假设：迷宫是连通的，即任意两个关键点之间都存在通路。如果迷宫不连通，那有些关键点之间就是不可达的，距离为-1。这种情况下最小生成树可能不存在。但一般题目会保证连通性，或者至少保证有解。

邻接矩阵的对角线设为0，自己到自己距离为0。对称位置的值应该相等，因为迷宫中的距离是对称的（从A到B和从B到A的最短路径长度相同）。如果你发现不对称，那说明BFS写错了。

3. 核心细节解析与实操要点

3.1 关键点编号与坐标映射

在扫描迷宫的时候，我们需要给每个关键点分配一个编号。可以用一个二维数组id[x][y]来记录，初始化为-1，遇到S或A就分配一个递增的编号，同时把坐标存到一个数组里。

int id[MAXN][MAXN]; struct Point { int x, y; } pts[MAXN]; int cnt = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (maze[i][j] == 'S' || maze[i][j] == 'A') { id[i][j] = cnt; pts[cnt].x = i; pts[cnt].y = j; cnt++; } } }

这段代码看起来简单，但有一个细节：S也要算作关键点。因为S是起始分裂点，它也需要被连通。有些人会忘记把S算进去，导致最后少了一个节点，答案偏小。

另外，输入的时候要注意行和列的读取方式。有些题目是先读列数再读行数，有些是反过来的。还有的题目用gets或者getline读整行，需要处理换行符。这些输入细节如果搞错了，后面全盘皆输。

3.2 BFS的距离计算与边界处理

BFS的核心代码大概长这样：

int dist[MAXN][MAXN]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; void bfs(int sx, int sy) { memset(dist, -1, sizeof(dist)); queue<pair<int,int>> q; dist[sx][sy] = 0; q.push({sx, sy}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue; if (maze[nx][ny] == '#') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } }

这段代码有几个值得注意的地方：

边界检查的顺序。先检查坐标是否越界，再检查是否是墙壁，最后检查是否已访问。顺序不能乱，否则可能数组越界。

maze的存储方式。如果用char maze[MAXN][MAXN]存储，要注意每行字符串的长度。有些题目每行末尾可能有\r（Windows换行），需要处理掉。建议读入后用cin或者scanf逐行读，避免gets的安全问题。

dist数组的大小。如果迷宫最大是50x50，那dist开[55][55]就够了。但如果题目没给范围，建议开大一点，比如[105][105]，防止越界。

队列元素类型。用pair<int,int>或者自定义结构体都行。C++17以上可以用结构化绑定auto [x, y] = q.front()，写起来更简洁。

3.3 Prim算法的实现细节

Prim算法的核心是维护一个lowcost数组，表示已选节点集合到未选节点的最小边权。每次从未选节点中选一个lowcost最小的加入集合，然后更新其他未选节点的lowcost。

int prim(int n) { int lowcost[MAXN]; bool visited[MAXN] = {false}; int total = 0; visited[0] = true; for (int i = 1; i < n; i++) { lowcost[i] = adj[0][i]; } for (int i = 1; i < n; i++) { int minVal = INF, minIdx = -1; for (int j = 0; j < n; j++) { if (!visited[j] && lowcost[j] < minVal) { minVal = lowcost[j]; minIdx = j; } } if (minIdx == -1) return -1; // 不连通 visited[minIdx] = true; total += minVal; for (int j = 0; j < n; j++) { if (!visited[j] && adj[minIdx][j] < lowcost[j]) { lowcost[j] = adj[minIdx][j]; } } } return total; }

这里有几个容易出错的地方：

初始化。lowcost初始化为起点到其他所有点的距离。visited数组初始化为false，然后把起点标记为true。

选最小值的循环。每次都要遍历所有未访问节点，找到lowcost最小的那个。如果找不到（minIdx == -1），说明图不连通，直接返回-1。

更新lowcost。加入新节点后，要遍历所有未访问节点，如果新节点到它们的距离更小，就更新lowcost。

INF的取值。如果边权最大可能到10000，那INF取0x3f3f3f3f（约10亿）就够了。不要取INT_MAX，因为加法可能溢出。

3.4 邻接矩阵的对称性与初始化

在构建邻接矩阵之前，需要先初始化。对角线设为0，其他位置设为INF。

for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { adj[i][j] = (i == j) ? 0 : INF; } }

然后对每个关键点跑BFS，更新邻接矩阵：

for (int i = 0; i < cnt; i++) { bfs(pts[i].x, pts[i].y); for (int j = 0; j < cnt; j++) { if (i == j) continue; int d = dist[pts[j].x][pts[j].y]; if (d != -1) { adj[i][j] = d; } } }

注意这里只更新了adj[i][j]，没有更新adj[j][i]。但因为BFS会跑n次，每次都会更新一行，所以最终矩阵是对称的。如果你只跑了一半的BFS想省时间，那就需要手动对称赋值。

提示：如果关键点数量是n，那BFS要跑n次，每次O(rowcol)。总时间复杂度是O(nrowcol + n^2)。对于n=100、row=col=50的情况，大约是1002500 + 10000 = 260000次操作，完全在可接受范围内。

4. 完整实操流程与代码实现

4.1 输入处理与迷宫解析

先来看输入部分。这类题目的输入格式通常是：第一行给出测试用例数，然后每个测试用例给出列数和行数，接着是迷宫本身。

#include <bits/stdc++.h> using namespace std; const int MAXN = 105; const int INF = 0x3f3f3f3f; int col, row; char maze[MAXN][MAXN]; int id[MAXN][MAXN]; int dist[MAXN][MAXN]; int adj[MAXN][MAXN]; struct Point { int x, y; } pts[MAXN]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1};

输入读取的时候要特别小心。有些题目用scanf("%d%d", &col, &row)读列和行，然后用getchar()吃掉换行，再逐行读迷宫。有些题目迷宫行内可能有空格，需要用getline或者fgets。

int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &col, &row); getchar(); // 吃掉换行 for (int i = 0; i < row; i++) { fgets(maze[i], MAXN, stdin); // 去掉末尾换行 int len = strlen(maze[i]); if (len > 0 && maze[i][len-1] == '\n') { maze[i][len-1] = '\0'; } } // ... 后续处理 } return 0; }

这里有一个坑：fgets会读入换行符，如果不处理掉，迷宫每行的最后一个字符就是\n而不是空格或墙壁，可能导致BFS判断出错。所以读完一行后要把末尾的换行符替换成\0。

另外，如果迷宫行的长度不足col，fgets可能读到下一行。这种情况一般不会出现，因为题目保证迷宫是矩形。但保险起见，可以在读入后检查一下长度。

4.2 关键点收集与编号

读入迷宫后，遍历每个格子，遇到S或A就分配编号：

int cnt = 0; memset(id, -1, sizeof(id)); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (maze[i][j] == 'S' || maze[i][j] == 'A') { id[i][j] = cnt; pts[cnt].x = i; pts[cnt].y = j; cnt++; } } }

注意memset(id, -1, sizeof(id))这行。id数组初始化为-1，表示该格子不是关键点。后面BFS的时候，如果遇到id不为-1的格子，就知道这是一个关键点。

4.3 BFS构建距离矩阵

对每个关键点跑BFS，填充邻接矩阵：

// 初始化邻接矩阵 for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { adj[i][j] = (i == j) ? 0 : INF; } } // 对每个关键点跑BFS for (int i = 0; i < cnt; i++) { // BFS memset(dist, -1, sizeof(dist)); queue<pair<int,int>> q; dist[pts[i].x][pts[i].y] = 0; q.push({pts[i].x, pts[i].y}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue; if (maze[nx][ny] == '#') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } // 更新邻接矩阵 for (int j = 0; j < cnt; j++) { if (i == j) continue; int d = dist[pts[j].x][pts[j].y]; if (d != -1) { adj[i][j] = d; } } }

这段代码是整道题的核心。BFS部分和前面讲的一样，关键是更新邻接矩阵的时候，只更新adj[i][j]，不更新adj[j][i]。因为外层循环会跑cnt次，每次更新一行，最终矩阵会自然对称。

但这里有一个潜在问题：如果某个关键点不可达（dist为-1），那adj[i][j]就保持INF。Prim算法遇到INF会怎么处理？如果图不连通，Prim会返回-1或者一个错误的结果。所以题目一般保证连通性，或者你需要额外判断。

4.4 Prim求最小生成树

最后跑Prim算法：

int prim(int n) { int lowcost[MAXN]; bool visited[MAXN]; memset(visited, false, sizeof(visited)); int total = 0; visited[0] = true; for (int i = 1; i < n; i++) { lowcost[i] = adj[0][i]; } for (int i = 1; i < n; i++) { int minVal = INF, minIdx = -1; for (int j = 0; j < n; j++) { if (!visited[j] && lowcost[j] < minVal) { minVal = lowcost[j]; minIdx = j; } } if (minIdx == -1) return -1; visited[minIdx] = true; total += minVal; for (int j = 0; j < n; j++) { if (!visited[j] && adj[minIdx][j] < lowcost[j]) { lowcost[j] = adj[minIdx][j]; } } } return total; }

如果cnt为0（迷宫中没有关键点），那直接输出0。如果cnt为1（只有一个关键点），那不需要连接，输出0。这两种边界情况要单独处理，否则Prim可能会出错。

if (cnt <= 1) { printf("0\n"); } else { printf("%d\n", prim(cnt)); }

4.5 完整代码整合与测试

把上面的代码片段整合起来，就是一个完整的解法。我用一个简单的测试用例来验证：

假设迷宫是：

##### #S A# #####

这里S和A之间有一个空格，距离为1。关键点有2个，邻接矩阵是[[0,1],[1,0]]。Prim的结果是1。输出应该是1。

再复杂一点：

####### #S#A#B# #######

这里S到A的距离是2（绕路），A到B的距离是2，S到B的距离是4。最小生成树选S-A和A-B，总权值4。

你可以用这些简单用例来验证代码的正确性。如果结果不对，先检查BFS的距离计算，再检查Prim的初始化。

5. 常见问题与排查技巧实录

5.1 BFS距离计算错误的排查

BFS写错是最常见的问题。典型症状是：某些关键点之间的距离算出来偏大或偏小，导致最终答案不对。

排查方法：手动模拟一个小迷宫，打印出BFS的dist数组，看看每个格子的距离是否正确。特别注意墙壁格子的距离应该是-1，起点的距离是0。

常见错误包括：

• 忘记标记起点已访问，导致起点被重复入队
• 方向数组写错，比如dx[]={1,-1,0,0}和dy[]={0,0,1,-1}对应的是上下左右，但如果写反了，移动方向就乱了
• 边界检查写错，比如nx >= row写成了nx > row
• 墙壁判断写错，比如把#写成了其他字符

实操心得：我习惯在BFS里加一个计数器，统计访问了多少个格子。如果访问的格子数等于迷宫的空格数，说明BFS覆盖了所有可达区域。如果少了，说明有地方写错了。

5.2 Prim算法结果偏大或偏小的原因

Prim结果偏大，通常是因为邻接矩阵中有一些边权是INF，但Prim没有正确处理，把INF加进了总权值。检查方法：在Prim的选边循环里打印每次选的minVal和minIdx，看看是否有INF被选中。

Prim结果偏小，通常是因为邻接矩阵初始化有问题，比如对角线没有设为0，或者某些不可达的边被错误地设成了0。检查方法：打印邻接矩阵，看看对称位置的值是否相等，对角线是否为0。

还有一种情况是关键点数量不对。比如忘记把S算进去，导致节点数少了一个，最小生成树的边数也少了一条，总权值自然偏小。

5.3 输入格式导致的诡异错误

输入格式是这类题目的一大坑。不同题目的输入格式可能略有不同，比如：

• 先给列数再给行数，还是先行后列
• 迷宫行内是否有空格
• 测试用例之间是否有空行
• 行末是否有\r

如果输入读错了，后面的所有计算都是白搭。排查方法：读入迷宫后，先打印出来看看，确认每个字符的位置和预期一致。

注意：如果使用fgets读入，一定要处理末尾的换行符。如果使用cin >> maze[i]，它会自动跳过空白字符，但遇到空格会停止读取，所以不适合读含空格的迷宫行。推荐用getline或fgets。

5.4 内存与时间优化的经验

如果关键点数量n比较大（比如接近100），BFS要跑100次，每次都要memset一个105x105的dist数组。memset的开销是O(105*105)≈11000，100次就是110万次操作，可以接受。

但如果n更大，比如500，那BFS要跑500次，memset的开销就是550万，加上BFS本身的开销，可能会超时。这时候可以考虑：

• 用时间戳代替memset，避免每次重置整个数组
• 用vector代替固定数组，减少内存占用
• 如果图是稀疏的，考虑用Kruskal代替Prim

不过在大多数竞赛题目中，n不会超过100，所以标准写法就够用了。

5.5 常见问题速查表

5.6 几个容易忽略的边界情况

只有一个关键点。如果迷宫中只有一个S或一个A，那不需要任何连接，答案是0。Prim算法在n=1时会直接返回0，但有些实现可能会出错，建议单独判断。

没有关键点。如果迷宫中既没有S也没有A，那答案也是0。这种情况虽然少见，但代码要能处理。

迷宫不连通。如果某些关键点之间不可达，那最小生成树不存在。题目一般会保证连通性，但如果你发现Prim返回-1，就要检查是不是迷宫本身不连通。

关键点数量为2。这时候最小生成树就是这两个点之间的距离，Prim会正确返回。但要注意邻接矩阵的对称性，如果只跑了一次BFS，adj[1][0]可能是INF。

6. 从这道题延伸出的通用解题框架

6.1 网格图上的多源最短路径问题

这道题的核心模式是：在网格图上，对多个源点分别跑BFS，构建完全图，然后求最小生成树。这个模式可以推广到很多类似问题。

比如，如果题目要求的是把所有关键点连通，但允许在某些格子上建造传送门（代价不同），那就变成了带权图的最小生成树问题。BFS部分不变，但边权需要重新计算。

再比如，如果题目要求的是从起点出发，经过所有关键点，最后回到起点，那就是旅行商问题（TSP），需要用状态压缩DP。但那是另一个话题了。

6.2 BFS与最短路算法的选择

在网格图上求最短路，BFS适用于边权为1的情况。如果边权不为1（比如某些格子移动代价是2），那就需要用Dijkstra或者0-1 BFS。

这道题中每走一步代价是1，所以BFS是最合适的。如果题目改成某些格子有不同代价，那就要换算法了。

提示：0-1 BFS适用于边权只有0和1的情况，用双端队列实现。如果边权是任意正整数，那就用Dijkstra加优先队列。

6.3 Prim与Kruskal的适用场景对比

在这道题中，因为BFS已经帮我们构建好了邻接矩阵，直接用Prim是最自然的。如果题目规模特别大，边数远小于n^2，那Kruskal可能更合适。

6.4 代码模板的复用与调整

这道题的代码可以作为一个模板，稍作修改就能用于其他类似题目。比如：

• 如果题目要求输出最小生成树的具体边，可以在Prim中记录每次选的边
• 如果题目要求判断是否连通，可以在Prim返回-1时输出特定信息
• 如果题目要求多组测试用例，把主逻辑封装成函数即可

我在做这类题时，习惯把BFS和Prim分别封装成独立函数，主函数只负责输入输出和调用。这样代码结构清晰，调试也方便。

6.5 调试技巧与验证方法

最后分享几个我在做这类题时的调试技巧：

小数据手动验证。构造一个3x3的迷宫，手动算出答案，然后和程序输出对比。如果不对，逐步打印中间结果。

打印邻接矩阵。在Prim之前打印邻接矩阵，看看是否对称、对角线是否为0、不可达的边是否为INF。

打印BFS的dist数组。对于第一个关键点，打印它到所有格子的距离，看看是否符合预期。

用随机数据对拍。写一个暴力解法（比如枚举所有生成树），和Prim的结果对比。虽然暴力解法慢，但对于小规模数据可以验证正确性。

检查数组大小。如果程序崩溃或结果诡异，先检查MAXN是否够大。迷宫的行列数、关键点数量都可能超过预期。

实操心得：我一般会在代码里加一些#ifdef DEBUG的打印语句，提交时注释掉。这样调试方便，又不会影响最终提交。

7. 我个人在实际操作中的体会

这道题我做过好几次，每次都有新的收获。最开始的时候，我只关注BFS和Prim各自的实现，觉得只要这两个算法写对了，答案就对了。但后来发现，真正容易出错的地方在建模和输入处理。

比如有一次，我忘记把S算作关键点，结果答案一直偏小。排查了半天才发现是关键点收集的问题。还有一次，输入的时候没有处理换行符，导致迷宫每行的最后一个字符是\n，BFS把\n当成了通道，距离算出来全是错的。

后来我养成了一个习惯：读完输入后先打印迷宫，确认每个字符的位置和预期一致。这个习惯帮我省了很多调试时间。

另外，Prim算法的初始化也很关键。我见过有人把lowcost初始化为0，结果Prim每次选的最小边都是0，总权值自然是错的。正确的做法是初始化为起点到其他点的距离，不可达的设为INF。

最后说一个关于时间复杂度的体会。这道题的标准解法是O(nrowcol + n^2)，其中n是关键点数量。如果n=100，row=col=50，总操作数大约是26万，完全没问题。但如果n=500，row=col=100，总操作数就是500*10000 + 250000 = 525万，可能会超时。这时候就需要考虑优化，比如用时间戳代替memset，或者用更高效的数据结构。

不过对于大多数竞赛题目来说，标准解法已经足够了。关键是把每个细节都写对，避免因为小错误导致整个程序出错。