1. 项目概述与问题引入“扩散”这道题是第十一届蓝桥杯C国赛的B题也是当年让不少选手印象深刻的一道经典题目。它表面上描述的是一个类似墨水在无限大网格上扩散的物理过程但内核却是一个标准的、需要巧妙建模的**广度优先搜索BFS**问题。很多刚接触算法竞赛的朋友一看到“无限大”、“扩散”这些词可能下意识会去想模拟整个扩散过程或者尝试寻找数学规律结果要么超时要么思路陷入死胡同。这道题的精妙之处恰恰在于它用了一个生活化的场景包装了一个对BFS算法理解深度和编程实现细节的考察。今天我们就来彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及我在实现过程中踩过的那些坑和总结出的技巧。题目大意可以抽象为在一个无限的二维网格平面上有若干个初始的“黑点”。在每一时刻每个黑点会向其上下左右四个相邻的网格格点扩散即将其染黑。问题是经过指定的时间后整个平面上有多少个格点被染黑了输入给出了初始黑点的坐标和时间限制我们需要输出这个总数。初看之下模拟扩散过程似乎是直观的。但稍加思考就会发现陷阱平面是无限的我们无法预知扩散的范围直接模拟每一时刻所有黑点的状态在时间较大时计算量会爆炸式增长。这正是题目引导我们使用BFS的原因——BFS天然适合处理这种“由近及远、层层推进”的扩散过程并且能确保每个点只被访问一次效率极高。理解这一点就拿到了解开这道题的第一把钥匙。2. 核心思路与算法选型分析2.1 为什么是BFS而不是DFS或模拟这是解决本题最根本的决策。让我们对比一下几种可能的思路暴力模拟为每个初始点维护一个当前边界集合每轮迭代将所有边界点向外扩张一格。这种方法在时间步数t较大时需要处理的点数量是O(N * t^2)级别的N是初始点数因为扩散范围近似一个菱形面积与t^2成正比。对于国赛级别的数据规模这几乎是不可行的。深度优先搜索DFSDFS适合探索路径或遍历连通分量但在此题中我们需要的是“最短时间”覆盖。一个点被染黑的时间等于离它最近的初始黑点的曼哈顿距离如果该距离小于等于时间t。DFS无法保证第一次访问某个点时就得到这个最短时间可能会绕远路导致重复访问和逻辑错误。广度优先搜索BFSBFS从多个源点初始黑点同时开始一层一层地向外探索。队列中每个节点记录了坐标和到达该点的时间。当一个点第一次被BFS访问到时所用的步数就是该点被染黑的最早时间。这正是我们需要的。我们只需要BFS到时间步数超过t为止然后统计所有被访问过即被染黑的点即可。时间复杂度约为O(被访问的点数)高效且准确。因此BFS是解决此类“多源点最短时间扩散/感染”问题的标准且最优工具。本题的核心就是如何正确、高效地实现这个多源BFS。2.2 关键建模离散化与无限平面的处理题目描述是“无限大平面”但计算机无法处理无限。我们必须找到一个有限的“边界”。这里需要利用一个核心观察在时间t之后所有被染黑的点其坐标 (x, y) 一定满足存在一个初始点 (xi, yi)使得 |x - xi| |y - yi| t。这意味着任何一个被染黑的点其坐标不会偏离任何一个初始点超过t的曼哈顿距离。因此我们可以计算出所有初始点在x轴和y轴方向上的最值然后向外扩展t的范围得到一个有限的矩形区域。在这个区域内进行BFS就足够了。具体步骤读取所有初始点坐标找到min_x, max_x, min_y, max_y。将搜索范围确定为[min_x - t, max_x t]和[min_y - t, max_y t]。这个矩形区域囊括了所有可能被染黑的点。在这个区域内进行BFS。注意坐标可能为负数所以我们在用数组模拟网格时需要进行坐标偏移将所有的点平移到非负索引上。例如定义一个足够大的二维数组vis标记是否访问和dist记录到达时间对于实际坐标(x, y)其对应的数组索引为(x OFFSET, y OFFSET)其中OFFSET是一个足够大的常数确保x OFFSET 0。注意这里的“足够大”需要仔细计算。OFFSET必须大于等于|min_x - t|和|min_y - t|的绝对值以确保平移后的索引非负。一个稳妥的做法是直接取OFFSET abs(min(min_x, min_y)) t 5多加一点余量防止边界问题。2.3 数据结构与算法流程设计基于以上分析我们可以设计出清晰的算法流程和数据结构数据结构vectorpairint, int sources: 存储初始黑点坐标。queuetupleint, int, int q: BFS队列元素为(x, y, time)表示在time时刻扩散到点(x, y)。vis[dx][dy]: 二维布尔数组标记点(dx, dy)是否已被访问已染黑。dx, dy是经过偏移后的数组索引。dist[dx][dy]: 二维整型数组记录点(dx, dy)被染黑的时间即BFS到达的步数。可以和vis数组合并用-1表示未访问。算法流程初始化读取初始点坐标和时间t。计算坐标范围确定偏移量OFFSET并初始化vis数组为falsedist数组为-1。多源BFS起点入队将所有初始点(sx, sy)加入队列标记其已访问到达时间为0。BFS循环当队列不为空时取出队首节点(x, y, time)。如果time t说明已经扩散到超过时间限制的点了后续点时间更大直接跳出循环。否则遍历(x, y)的四个邻居(nx, ny)上下左右。检查(nx, ny)是否在计算出的有限矩形区域内并且vis为false未访问。如果满足条件则标记vis为truedist为time 1并将(nx, ny, time 1)入队。统计结果BFS结束后遍历整个vis数组统计所有值为true的格子数量即为所求答案。3. 代码实现与逐行解析理解了思路我们来看具体的C实现。我会将关键代码拆解并解释每一部分的意图和注意事项。#include iostream #include vector #include queue #include tuple #include cstring // 用于memset using namespace std; // 方向数组表示上下左右四个方向的偏移量 const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int main() { // 假设输入格式第一行是初始点个数n和时间t后面n行是每个点的坐标 int n, t; cin n t; vectorpairint, int sources(n); int min_x 0x3f3f3f3f, max_x -0x3f3f3f3f; int min_y 0x3f3f3f3f, max_y -0x3f3f3f3f; // 1. 读取数据并确定坐标范围 for (int i 0; i n; i) { int x, y; cin x y; sources[i] {x, y}; min_x min(min_x, x); max_x max(max_x, x); min_y min(min_y, y); max_y max(max_y, y); } // 2. 计算搜索边界和偏移量 // 扩散最远距离是t所以边界需要扩展t int left_bound min_x - t; int right_bound max_x t; int down_bound min_y - t; int up_bound max_y t; // 计算网格的宽度和高度以格点计需要1 int width right_bound - left_bound 1; int height up_bound - down_bound 1; // 确定偏移量使得(left_bound, down_bound)映射到数组索引(0, 0) int offset_x -left_bound; // 实际坐标x对应的数组索引 idx_x x offset_x int offset_y -down_bound; // 实际坐标y对应的数组索引 idx_y y offset_y // 3. 初始化访问数组和距离数组 // 使用vector动态创建二维数组避免栈溢出如果范围很大 vectorvectorbool vis(width, vectorbool(height, false)); // 也可以用一个dist数组这里我们用vis和队列里的时间信息就够了 queuetupleint, int, int q; // (x, y, time) // 4. 多源BFS初始化所有起点入队 for (auto [sx, sy] : sources) { int idx_x sx offset_x; int idx_y sy offset_y; vis[idx_x][idx_y] true; q.push({sx, sy, 0}); // 起点时间为0 } // 5. BFS主循环 long long ans 0; // 答案可能很大用long long while (!q.empty()) { auto [x, y, time] q.front(); q.pop(); // 当前点是在time时刻被染黑的它应该被计入答案 // 注意这里统计时机很重要要在处理该点时计数。 if (time t) { ans; } else { // 如果当前点时间已经超过t那么队列后面的点时间都time肯定也超过t // 可以提前结束BFS但这里我们选择继续处理完队列中可能存在的timet的点。 // 更严谨的做法是入队时判断这里为了逻辑清晰在出队时判断并停止扩散。 continue; } // 如果已经达到时间t则不再向四周扩散因为扩散需要时间1 if (time t) { continue; } // 向四个方向扩散 for (int d 0; d 4; d) { int nx x dirs[d][0]; int ny y dirs[d][1]; int ntime time 1; // 检查新点是否在预计算的边界内 if (nx left_bound || nx right_bound || ny down_bound || ny up_bound) { continue; } // 转换为数组索引 int n_idx_x nx offset_x; int n_idx_y ny offset_y; // 如果该点未被访问过则标记并入队 if (!vis[n_idx_x][n_idx_y]) { vis[n_idx_x][n_idx_y] true; q.push({nx, ny, ntime}); } } } // 6. 输出结果 cout ans endl; return 0; }关键点解析边界计算与偏移left_bound, right_bound等变量定义了我们需要进行BFS的物理坐标范围。offset_x和offset_y是关键它们将物理坐标线性映射到数组索引[0, width)和[0, height)之间使得我们可以用固定大小的二维数组来标记访问状态。队列元素我们选择在队列中存储原始物理坐标(x, y)和时间time而不是数组索引。这样在判断邻居是否越界时更直观用物理边界判断只在访问vis数组时才转换为索引。这减少了思维转换的负担。答案统计时机注意ans是在出队时且time t的条件下进行的。为什么不在入队时统计因为BFS的队列可能包含时间超过t的点如果我们在入队时不加判断。在出队时判断可以确保我们只统计在t时刻及之前被染黑的点。另一种等价的写法是在BFS结束后遍历整个vis数组统计所有在t时刻及之前被访问的点这需要dist数组记录时间。提前终止条件代码中有两处continue。第一个是当time t时该点本身不计入答案并且也不再从其扩散因为它本就是在t时刻后才被访问的。第二个是当time t时该点计入答案但不再从它继续扩散因为扩散一步需要时间1会超过t。这两个剪枝操作能有效减少不必要的队列操作。4. 性能优化与边界情况探讨上述代码是清晰易懂的版本但在实际竞赛中我们还可以从以下几个方面进行优化和深入思考4.1 空间优化使用一维数组或更紧凑的存储当t很大时我们定义的矩形区域边长约为(max_x-min_x2t)面积是边长的平方。如果这个值达到数万那么vis二维数组可能会占用数百MB甚至更多的内存bool类型通常占1字节。这时有几种优化思路使用bitset或手写位标记一个bool占1字节8位而一个点只需要1位信息是否访问。我们可以用vectorunsigned int或vectorunsigned long long来模拟二维位数组将内存占用减少到原来的1/8或1/64。使用哈希表unordered_set或手写哈希表只存储被访问过的点坐标。在BFS过程中需要频繁查询一个点是否被访问哈希表的平均时间复杂度是O(1)。这对于扩散范围很广但实际被染黑的点相对稀疏的情况非常有效。但哈希表常数较大需要权衡。使用坐标压缩离散化由于点的坐标是整数且范围已知我们可以将x坐标和y坐标分别排序去重得到两个映射表。这样可以将坐标值映射到[0, 新范围)的连续整数上大幅减小数组尺寸。但BFS中需要频繁根据物理坐标查询映射后的索引会增加一些代码复杂度。对于蓝桥杯的评测环境通常用二维bool数组是足够的但了解这些优化手段是进阶必备。4.2 时间复杂度的精确分析设初始点数为n扩散时间为t。最坏情况下所有被染黑的点构成一个大致包含O(t^2)个点的菱形区域从一个点扩散。对于多源扩散最终被访问的点数V是所有这些菱形区域的并集的点数。最坏情况是初始点相距很远V ≈ n * O(t^2)。BFS的时间复杂度是O(V E)其中E是边数每个点有4条边所以大约是O(4V) O(V)。因此算法复杂度约为O(n * t^2)。在t达到几百n很小的情况下这个复杂度是可以接受的。如果t更大比如上千就需要考虑更优的数学方法如计算几何求多个菱形的并集面积但这已远超本题范围。4.3 常见“坑点”与调试技巧整数溢出ans是染黑点的总数。当t较大时这个数可能超过int的范围2^31-1。例如从一个点开始扩散t2000时覆盖的点数约为2*t*(t1)1已经超过400万多个源点叠加会更大。务必使用long long类型存储答案。数组越界这是最易出错的地方。务必仔细检查坐标偏移和边界判断。检查1计算width和height时是right_bound - left_bound 1这个1很容易漏掉。检查2数组索引n_idx_x和n_idx_y必须在[0, width)和[0, height)之内。我们的判断if (nx left_bound ...)保证了物理坐标在范围内加上偏移后索引自然在范围内这是一个双重保障。调试技巧可以在BFS开始时打印出left_bound, right_bound, offset_x, offset_y等关键参数。对于小规模测试用例可以手动模拟打印出每一步队列的状态和vis数组比对是否与预期一致。多源点重复题目没有说明初始点是否重复。如果重复我们的代码中同一个点会被多次标记vis和入队但由于vis检查只有第一次会生效后续的会被跳过不影响结果。ans也会因重复入队出队而被重复累加吗注意ans是在出队时累加的一个点即使作为多个源点被多次入队也只会因为vis标记而第一次被访问到时才真正执行扩散和后续入队逻辑。但是它可能作为不同的“源点代表”被多次加入队列。在出队时如果vis已经为真我们上面的代码逻辑会直接跳过该点的扩散但仍然会执行ans。这会导致重复计数因此更安全的做法是在出队并判断timet后立即检查该点的vis状态或dist值如果发现不是第一次访问即当前时间time大于dist[x][y]则跳过本次处理。或者更简单的方法是不在出队时统计ans而在BFS结束后遍历dist数组统计所有dist[i][j] ! -1 dist[i][j] t的点。这是更推荐的做法逻辑更清晰也能正确处理源点重复的情况。时间判断逻辑上面代码中我们在出队时判断if (time t)来累加ans并在time t时停止扩散。这个逻辑对于单一起点是正确的。但对于多源点一个点可能被更近的源点以更短的时间t1访问然后又被另一个源点以时间t2(t2 t1) 再次尝试访问。我们的vis数组阻止了第二次访问所以没问题。但关键在于这个点被计入答案的时间应该是t1而我们的统计是在它第一次出队时时间为t1进行的所以正确。5. 扩展思考与变种问题解完一道题如果能进行举一反三的思考收获会大得多。基于“扩散”模型我们可以想到一些相关的变种问题带权扩散如果向不同方向扩散的速度不同例如上下方向1格/时刻左右方向2格/时刻这就变成了一个多源最短路径问题可以使用**优先队列BFSDijkstra算法**来解决。队列中按“到达时间”排序每次取出时间最小的点进行松弛。有障碍物的扩散在网格中有些格子是障碍物无法被扩散也无法穿过。这依然可以用BFS解决只是在扩散到邻居点时需要检查该邻居点不是障碍物。这变成了一个在多源点、有障碍地图上的连通区域搜索问题。求达到某个覆盖比例的最短时间问题变为“至少需要多少时间才能让被染黑的格子数量达到总格子数的K%”。这可以通过二分答案结合BFS来求解。二分猜测时间T然后用BFS模拟扩散T时间计算覆盖点数判断是否达到要求。连续空间扩散如果平面是连续的初始点是几个圆形区域每个圆形区域随时间t半径匀速扩大。问t时刻后这些圆形区域的并集面积。这就变成了计算几何问题需要求多个圆的并集面积可以使用扫描线或几何剖分的方法复杂度陡然上升。通过解决“扩散”这道题我们巩固了多源BFS的模板学习了如何将无限问题转化为有限问题设定边界并掌握了坐标偏移这一常用技巧。在竞赛中遇到“感染”、“传播”、“最短时间覆盖”这类关键词要能立刻联想到BFS。实现时细心处理边界、偏移和统计逻辑就能稳稳拿下这类题目。