1. 项目概述从“扩散”到“连通”的算法建模看到“蓝桥杯2020年第十一届C/C国赛B组第二题-扩散”这个标题很多参加过蓝桥杯的同学估计会心一笑或者眉头一皱。这绝对是一道经典的、能拉开差距的题目。它披着“扩散”这个物理现象的外衣内核却是一个标准的、需要一点巧思的算法问题。题目通常不会给你一个复杂的物理公式去模拟粒子运动而是会抽象成一个更纯粹的计算机模型在无限的二维网格平面上有若干个初始点每个时间单位这些点会向其上、下、左、右四个方向各扩散一格。问题最终会问经过指定的时间后有多少个网格点被“感染”或覆盖了或者所有初始点形成的“连通区域”需要多久才能完全连成一片这本质上是一个模拟Simulation与搜索Search的结合体。最直接的思路就是模拟每一时刻的扩散过程但“无限平面”和“长时间模拟”这两个词组合在一起就是对朴素模拟算法性能的终极拷问。因此这道题考察的核心就在于你能否跳出“逐帧模拟”的思维定式转而从几何或图论的角度用更高效的方法来解决问题。常用的解法包括BFS广度优先搜索和基于曼哈顿距离的数学分析。前者是标准的图搜索算法后者则利用了网格世界的特殊几何性质能将问题复杂度从与时间相关降低到仅与初始点数相关。这道题适合所有正在准备算法竞赛尤其是蓝桥杯、力扣的C/C选手无论是想巩固BFS的应用还是学习如何将实际问题抽象为数学模型它都是一个绝佳的练手材料。接下来我将彻底拆解这道题的两种核心思路并分享在实现过程中那些容易踩坑的细节和性能优化的技巧。2. 核心思路拆解BFS与曼哈顿距离的博弈面对“扩散”问题我们首先要建立正确的数学模型。题目给定的通常是一个二维坐标平面点坐标均为整数。扩散规则是每一秒所有已被覆盖的点会同时向其四邻域上、下、左、右扩散一格。这里的关键词是“同时”这意味着新覆盖的点在下一秒也会立即加入扩散源的行列。2.1 思路一广度优先搜索BFS这是最符合直觉的图论建模方法。我们可以将每一个整数坐标点(x, y)视为图中的一个节点。如果点A和点B的曼哈顿距离为1即|Ax - Bx| |Ay - By| 1则认为它们之间存在一条无向边。扩散过程就是从初始的若干个源点开始在这张无限的网格图上进行多源BFS的过程。BFS为什么可行BFS的特性是“层层推进”。从源点开始第一层访问距离源点为1的点第二层访问距离为2的点以此类推。这完美对应了扩散的“秒数”。第t秒后被覆盖的点就是所有距离任意一个源点的最短路径长度小于等于t的点。多源BFS可以一次性将所有源点放入初始队列它们都属于第0层。然后进行标准的BFS当遍历的层数达到目标时间T时所有被访问过的节点总数就是答案。这个思路的优势与挑战优势在于直观代码模板化不易出错。挑战在于空间和时间的边界。由于平面是无限的我们不能真的创建一个无限的数组。通常需要估算一个足够大的边界或者使用std::unordered_set或std::set来存储已访问的点坐标对。对于时间T较大的情况BFS需要扩展的节点数量大约与T^2成正比因为面积近似于一个半径为T的圆的面积量级为O(T^2)。如果T很大比如上千节点数可能达到百万级在竞赛环境下对时间和空间都是考验。2.2 思路二曼哈顿距离与几何分析这是一种更巧妙、更高效的方法它直接利用了网格世界的几何特性——曼哈顿距离。在只能上下左右移动的网格中两点(x1, y1)和(x2, y2)之间的最短路径长度就是曼哈顿距离|x1-x2| |y1-y2|。如何用曼哈顿距离解决扩散问题考虑一个点P(x, y)。它被覆盖的时间取决于离它最近的那个初始源点需要多久才能扩散到它。假设有n个初始源点S1, S2, ..., Sn。那么点P被覆盖的时间t_P就是t_P min( distance(P, S1), distance(P, S2), ..., distance(P, Sn) )其中distance是曼哈顿距离。那么问题“经过时间T后有多少个点被覆盖” 就等价于“有多少个整数点P满足min(distance(P, Si)) T”这带来了一个更深刻的问题转换我们不需要模拟过程只需要判断每个点是否满足上述不等式。但枚举平面上所有的点仍然是无限的。这里需要第二个关键观察被覆盖的区域形状。在曼哈顿距离下一个源点S在时间t内能覆盖的区域是一个中心在S、对角线水平的正方形更准确叫法是菱形但在坐标轴对齐的视图下是旋转45度的正方形。这个区域内的点满足|x - Sx| |y - Sy| t。那么n个源点共同覆盖的区域就是n个这样的曼哈顿距离“菱形”的并集。我们的问题转化为求n个菱形的并集在tT时包含了多少个整数坐标点。对于只有少数几个源点比如题目常见的4个的情况我们可以通过计算几何的方法来求并集面积整数点数量。例如可以计算所有源点两两之间“影响范围”的交界但实现较为复杂。一个更工程化的方法是既然源点很少我们可以枚举一个足够大的矩形区域对这个区域内的每一个点计算其到所有源点的最小曼哈顿距离如果T则计数1。这个矩形的范围需要根据源点坐标和T来估算通常上下左右各扩展T的距离即可包含所有可能被覆盖的点。曼哈顿距离法的优势时间复杂度与源点数量n、时间T以及我们枚举的区域大小有关。当n很小≤4而T很大时它枚举的点数大约是O((T)^2)和BFS类似。但其优势在于概念清晰直接揭示了问题的几何本质。无需队列和状态维护实现更简单不易在BFS的队列操作和状态标记上出错。易于并行计算每个点的判断是独立的虽然竞赛中用不到但思想有启发性。实操心得选择哪种思路在竞赛中我的选择策略是如果题目明确要求输出T秒后的点数且T可能很大1000但初始点很少≤4优先考虑曼哈顿距离枚举法。我们需要快速估算枚举边界找到所有初始点中最小和最大的x,y然后向四周扩展T格形成枚举矩形。这个矩形内的点数在可控范围内。如果T不大500或者初始点数量较多BFS是更稳妥的选择。因为BFS可以处理任意多的源点且代码模板化。使用std::queue和std::unordered_set或自己编码的哈希函数来记录已访问点是标准做法。如果问题问的是“最早何时所有点连通”这本质是求所有点对之间曼哈顿距离最大值的某种关系例如对于两个点它们连通所需时间是曼哈顿距离的一半向上取整。对于多个点可以转化为计算曼哈顿距离下的“最小生成树”的最大边权这需要用到并查集和生成树算法Kruskal思路就更进一步了。但国赛B组第二题通常不会这么复杂一般还是求固定时间后的点数。3. 基于BFS的详细实现与避坑指南我们首先深入最通用的BFS解法。假设题目输入是四个初始点坐标(x1,y1), (x2,y2), (x3,y3), (x4,y4)和一个时间T要求输出T秒后被覆盖的点数。3.1 数据结构与状态表示在无限的网格上进行BFS首要问题是如何表示和记录一个点的状态是否已被访问。方案一数组偏移法推荐高效这是竞赛中最常见的方法。虽然平面是无限的但经过T秒后扩散范围不可能超过初始点的坐标范围± T。因此我们可以提前计算一个有限的网格窗口。找到所有初始点中x和y的最小值min_x,min_y。确定网格的左上角偏移offset_x min_x - T,offset_y min_y - T。这是为了确保所有可能被覆盖的点都有非负的数组索引。计算网格的宽度和高度width (max_x - min_x) 2*T 1,height (max_y - min_y) 2*T 1。1是因为包含边界。创建一个二维布尔数组visited[height][width]所有元素初始化为false。对于任意一个实际坐标(real_x, real_y)其对应的数组索引为index_x real_x - offset_xindex_y real_y - offset_y在BFS入队前先检查index_x和index_y是否在数组边界内然后检查visited[index_y][index_x]注意行优先还是列优先。方案二使用STL容器存储坐标对如果不想计算复杂的偏移可以使用std::setstd::pairint, int或std::unordered_set来存储已访问的坐标。set基于红黑树插入和查找是O(log n)unordered_set基于哈希表平均O(1)。但自定义pair的哈希函数需要一些技巧C11后可以特化std::hash或者直接用set更省事。避坑指南坐标哈希与性能使用unordered_set时必须为std::pairint, int提供哈希函数。一个简单通用的方法是struct PairHash { template typename T1, typename T2 std::size_t operator() (const std::pairT1, T2 p) const { auto h1 std::hashT1{}(p.first); auto h2 std::hashT2{}(p.second); // 一个简单的组合方式注意这里异或操作在哈希值相近时可能效果不好 // 更稳健的做法是像 boost.hash_combine 那样 return h1 ^ (h2 1); } }; std::unordered_setstd::pairint, int, PairHash visited;对于大规模节点10^5unordered_set的哈希冲突可能成为性能瓶颈。此时数组偏移法的连续内存访问效率要高得多是首选。我个人的经验是在蓝桥杯这种时间限制严格的比赛中只要内存允许估算数组大小在10^6量级以内尽量使用数组。3.2 多源BFS的实现模板以下是使用数组偏移法的C代码框架#include iostream #include queue #include vector using namespace std; // 方向数组上下左右 const int dx[4] {0, 0, -1, 1}; const int dy[4] {1, -1, 0, 0}; struct Point { int x, y; int step; // 从某个源点扩散到该点所用的时间 }; int main() { // 假设有4个初始点 vectorpairint, int sources {{0,0}, {2020,11}, {11,14}, {2000,2000}}; int T 2020; // 扩散时间 // 1. 计算边界和偏移量 int min_x sources[0].first, max_x sources[0].first; int min_y sources[0].second, max_y sources[0].second; for (auto p : sources) { min_x min(min_x, p.first); max_x max(max_x, p.first); min_y min(min_y, p.second); max_y max(max_y, p.second); } int offset_x min_x - T; int offset_y min_y - T; int width (max_x - min_x) 2 * T 1; int height (max_y - min_y) 2 * T 1; // 2. 初始化访问数组和队列 vectorvectorbool visited(height, vectorbool(width, false)); queuePoint q; // 3. 多源入队 for (auto src : sources) { int idx_x src.first - offset_x; int idx_y src.second - offset_y; // 安全检查理论上应该在边界内 if (idx_x 0 idx_x width idx_y 0 idx_y height) { visited[idx_y][idx_x] true; q.push({src.first, src.second, 0}); // 源点步数为0 } } long long count sources.size(); // 初始点本身已被覆盖 // 4. BFS遍历 while (!q.empty()) { Point cur q.front(); q.pop(); // 如果当前点的时间已经达到T则从其出发的扩散不会产生新的在T时刻内的点 // 但注意BFS是按层遍历的当cur.step T时下一层就是T1所以这里判断是否小于T if (cur.step T) { continue; // 关键剪枝时间已到不再从该点向外扩展 } for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; int n_step cur.step 1; int idx_x nx - offset_x; int idx_y ny - offset_y; // 检查是否在枚举的网格范围内且未被访问 if (idx_x 0 idx_x width idx_y 0 idx_y height) { if (!visited[idx_y][idx_x]) { visited[idx_y][idx_x] true; count; // 覆盖点数1 q.push({nx, ny, n_step}); } } } } cout 在时间 T 后覆盖的点数为: count endl; return 0; }关键点解析step的含义cur.step表示从最近的源点扩散到当前点cur所需的时间。当cur.step T时意味着这个点正好是在第T秒被覆盖的。从它出发再扩散一步产生的新点将在T1秒被覆盖这已经超出了题目要求。因此if (cur.step T) continue;这行代码是一个重要的剪枝能显著减少不必要的入队操作。计数时机初始点数量在开始时就计入count。之后每一个新访问到的点即第一次被扩散覆盖的点都立即计数。这保证了我们计算的是所有在时间T内含被覆盖的点。边界检查我们只在我们预先声明的visited数组范围内进行检查。这基于一个假设T秒后覆盖点不会超出这个范围。这个假设在数学上是成立的因为我们的偏移量是min_x - T和min_y - T范围是± T。3.3 BFS解法的性能分析与优化对于T2020初始点坐标范围在0到2000之间的情况width和height大约在6000左右2000 2*2020 ≈ 6040。那么visited数组大小约为6000 * 6000 36,000,0003600万个布尔值。在C中一个vectorbool可能会进行位压缩实际内存占用可能小于3600万字节但访问可能稍慢。也可以使用vectorchar或vectorint但内存会增大。优化建议使用vectorchar代替vectorboolvectorbool是C标准库的一个特化版本它每个元素只占一个bit但这也导致其不能返回真正的引用且访问速度可能较慢。在性能关键的竞赛代码中使用vectorchar1字节是更稳妥的选择虽然内存占用是vectorbool的8倍但对于3600万元素也就是约36MB通常在竞赛内存限制如256MB内是可以接受的。vectorvectorchar visited(height, vectorchar(width, 0)); // 访问时用 visited[y][x] 1 判断循环展开与局部变量在BFS的核心循环中频繁访问visited、dx、dy。确保这些数组在内存中连续编译器优化会更好。将width,height,offset_x,offset_y等定义为局部变量或常量。队列的选择std::queue通常足够快。如果追求极致可以使用手写的循环队列数组但代码复杂度会增加除非性能瓶颈确实在队列操作上通常不会。4. 基于曼哈顿距离的枚举法实现当初始点数量极少比如4个时曼哈顿距离枚举法代码更简洁。我们不需要维护队列和状态转移只需要两层循环枚举一个矩形区域内的所有点并对每个点计算到所有源点的最小曼哈顿距离。实现步骤确定枚举边界和BFS方法一样计算min_x, max_x, min_y, max_y然后向四周扩展T。双重循环枚举for x from min_x - T to max_x T;for y from min_y - T to max_y T。核心判断对每个(x, y)计算其到所有源点的曼哈顿距离取最小值min_dist。计数如果min_dist T则该点在T时刻被覆盖计数器加一。C代码示例#include iostream #include vector #include cmath #include climits using namespace std; int manhattan(int x1, int y1, int x2, int y2) { return abs(x1 - x2) abs(y1 - y2); } int main() { vectorpairint, int sources {{0,0}, {2020,11}, {11,14}, {2000,2000}}; int T 2020; int min_x sources[0].first, max_x sources[0].first; int min_y sources[0].second, max_y sources[0].second; for (auto p : sources) { min_x min(min_x, p.first); max_x max(max_x, p.first); min_y min(min_y, p.second); max_y max(max_y, p.second); } long long count 0; // 枚举矩形区域 for (int x min_x - T; x max_x T; x) { for (int y min_y - T; y max_y T; y) { int min_dist INT_MAX; for (auto src : sources) { int dist manhattan(x, y, src.first, src.second); if (dist min_dist) { min_dist dist; // 如果min_dist已经小于等于T可以提前结束内层source循环小优化 if (min_dist T) { break; } } } if (min_dist T) { count; } } } cout 在时间 T 后覆盖的点数为: count endl; return 0; }复杂度分析假设源点数量为n枚举区域的边长约为L (max_x-min_x 2T) 1枚举点总数约为L^2。对于每个点我们需要计算n次曼哈顿距离。因此总时间复杂度为O(n * L^2)。当n4,T2020,L≈6000时计算量约为4 * 36,000,000 144,000,0001.44亿次曼哈顿距离计算。每次计算是两次绝对值和一次加法在现代CPU上运行是很快的通常在1秒内可以完成。这比BFS的队列操作和状态检查可能还要快一些因为循环结构非常规整利于CPU缓存和预测。注意事项整数溢出与计数类型无论是BFS还是枚举法最终覆盖的点数可能非常大。例如当T2020时覆盖面积量级在10^7千万级别。因此用于计数的变量如代码中的count必须使用long long类型64位整数避免使用int32位导致溢出产生错误结果。这是竞赛中一个非常经典的陷阱。5. 常见问题与调试技巧实录在实际编写和调试这类扩散问题的代码时我踩过不少坑也总结了一些调试技巧。5.1 问题一答案比预期小很多可能原因边界计算错误这是最常见的原因。在计算min_x, max_x时漏掉了某个源点或者± T的范围算错。调试方法打印出你计算出的min_x, max_x, min_y, max_y以及offset_x, offset_y, width, height。用一个小T比如1或2和简单的源点如(0,0), (1,1)手动模拟看你的枚举或BFS范围是否包含了所有应被覆盖的点。BFS剪枝条件错误在BFS代码中如果错误地将if (cur.step T) continue;写成了if (cur.step T) continue;那么当cur.step T时还会继续从该点扩散这会产生T1时刻的点但我们的计数只发生在入队时所以不会多计。反之如果写成if (cur.step T) continue;那么cur.step T的点仍然会扩散产生T1的点但如果我们只对step T的点计数在入队时判断n_step T才计数则不会出错。但最清晰的逻辑还是当cur.step T时它已经是最后一刻被覆盖的点不应该再作为扩散源。数组索引越界在BFS中计算idx_x nx - offset_x后没有检查是否在[0, width)和[0, height)范围内就直接访问visited数组可能导致运行时错误段错误或访问到非法内存使得一些本该被访问的点被跳过。务必加上边界检查。5.2 问题二答案比预期大一些可能原因重复计数在BFS中一个点可能被多个邻居在同一时刻发现并入队。如果你在将点加入队列时没有立即标记为已访问visited而是等到从队列中取出时才标记那么这个点可能会被多次加入队列导致重复计数。必须遵守“入队即标记”的原则。初始点重复题目给出的源点坐标可能有重复虽然蓝桥杯题目数据通常不会这样但自己测试时要注意。如果源点重复在BFS初始化入队时重复的点会导致visited被多次标记为true但计数count却增加了多次。需要在初始化时去重或者使用set来存储初始点。5.3 问题三程序运行超时或内存超限可能原因及优化T或坐标值过大导致width和height巨大visited数组内存爆炸。例如如果坐标值本身是10^9级别T也是10^9那么数组法就完全不可行了。此时必须使用基于unordered_set的BFS或者转用曼哈顿距离的数学方法如果源点极少。但通常竞赛题会控制数据范围。BFS剪枝不足如果没有if (cur.step T) continue;这个剪枝BFS会无限制地扩散下去直到队列为空即覆盖整个无限平面这显然会超时和超内存。STL容器效率如果使用setpairint,int且节点数巨大10^5插入和查找的O(log n)开销会变得明显。unordered_set在哈希函数良好时更优但自定义哈希函数不当可能导致冲突严重退化为O(n)。对于已知范围的问题数组法是性能最优解。枚举法循环过多如果枚举的矩形区域过大且源点数量n也不少O(n*L^2)的复杂度可能超标。这时需要审视是否能用更巧妙的数学方法例如求多个菱形的并集面积但这通常超出蓝桥杯B组难度。5.4 调试与测试技巧小数据测试永远先用最小的、能手动验证的数据测试。例如设置T0答案应等于初始点数。设置T1源点为(0,0)手动计算应覆盖5个点(0,0), (0,1), (0,-1), (1,0), (-1,0)。对称性测试如果源点是对称的比如(0,0), (10,0)那么覆盖区域也应对称。可以输出中间结果如某个y值下所有被覆盖的x来检查。对比两种方法如果你时间充裕可以分别用BFS和曼哈顿枚举法实现用同一组随机生成的小数据T较小进行对拍确保两者结果一致。这是验证算法正确性的有效手段。输出中间变量在计算边界后打印出min_x, max_x, width, height等值看是否符合预期。在BFS中可以在每扩展一层后打印当前队列大小和已覆盖点数观察增长趋势是否合理。6. 从本题延伸的算法思维提升“扩散”题虽然解出来了但它的价值远不止于此。它为我们打开了几个重要的算法思维窗口1. 距离度量与搜索算法曼哈顿距离是“网格世界”的天然度量。与之相关的还有切比雪夫距离max(|dx|, |dy|)。BFS是解决基于曼哈顿距离的最短路径问题的利器。反之如果你遇到的问题是欧几里得距离直线距离那么BFS就不适用了可能需要Dijkstra或A*算法。2. 多源BFS的广泛应用多源BFS是一个经典模型。它不仅可以用来模拟扩散还可以解决诸如“多个起火点同时蔓延的最短时间”、“多个起点同时搜索最近目标”等问题。其核心思想是将多个源点同时放入队列并标记初始距离为0。这样BFS第一次访问到任何一个其他节点时该节点的距离就是离它最近源点的距离。3. 离散与连续的思考这道题是离散的整数点。如果问题变成在连续平面上扩散例如圆形扩散我们可能需要用到计算几何的方法。离散化是算法竞赛中连接离散与连续的桥梁。例如如果扩散速度不同或者有障碍物问题就变成了带权重的BFS或Dijkstra。4. 性能估算与算法选择这是本题带给我们的最实战的经验。看到问题不要立刻开写。先估算数据规模时间T多大决定扩散范围初始点n多少决定计算复杂度坐标范围多大决定数组大小 基于这些估算再决定是用O(T^2)的模拟/BFS还是用O(n * R^2)的枚举抑或是寻找O(n^2)或O(n log n)的数学解法。在我个人的刷题经验中像“扩散”这类题目是区分“只会套模板”和“真正理解算法”的试金石。它要求你不仅会写BFS还要知道为什么BFS在这里有效它的局限是什么以及什么时候可能有更优的解法。把这道题吃透以后再遇到“病毒传播”、“火焰蔓延”、“多起点最短路径”这类问题你就能一眼看穿本质快速找到解题钥匙。最后记得在竞赛中long long是你的好朋友边界检查是你的护身符小数据测试是你避免罚时的最后防线。