1. 问题重述与核心思路拆解“扩散”这道题是2020年蓝桥杯国赛C B组的一道经典题目。很多初次接触的同学看到“扩散”二字可能会联想到物理现象或者图像处理但在这道题里它被抽象成了一个非常典型的计算几何与图论搜索相结合的问题。我们先抛开代码用最直白的话把题目意思和我们要做的事情讲清楚。想象一个无限大的网格纸每一个格子用一个整数坐标(x, y)来表示。最开始有四个点被“感染”了或者说被“点亮”了。题目告诉我们每一分钟每一个已被感染的点会向它的上、下、左、右四个相邻的格子即曼哈顿距离为1的格子扩散感染。一个新格子被感染后在下一分钟也会加入扩散的行列。我们的目标很简单计算出在第2020分钟结束时或者说从第0分钟开始经过2020分钟后有多少个格子被感染了。这听起来是不是有点像“细胞分裂”或者“病毒传播”没错其本质就是一个在离散网格上的传播过程。最直接的思路就是模拟我们有一个集合来存放所有已被感染的点每分钟遍历这个集合把每个点的四个邻居加入集合直到时间到2020分钟最后统计集合的大小。但是这里有一个巨大的陷阱。如果真去模拟一个无限大的平面哪怕只模拟2020分钟感染范围也会是一个边长超过4000的巨大正方形区域点数量级在千万以上。在比赛环境下无论是时间还是内存直接进行BFS广度优先搜索模拟都是不可行的。我们必须找到更巧妙的方法。这道题的精髓就在于它考察你是否能跳出“模拟”的惯性思维转而利用曼哈顿距离和离散几何的性质将问题转化为一个判断点是否可达的数学问题。核心思路如下任何一个坐标点(x, y)如果它能被初始的某个感染点(x0, y0)在2020分钟内“扩散”到那么它们之间的曼哈顿距离必须满足|x - x0| |y - y0| 2020。曼哈顿距离也叫出租车距离就是两点在标准坐标系上的绝对轴距之和。为什么是这个条件因为每分钟扩散一步每一步只能改变一个坐标值1个单位上/下/左/右。所以从(x0, y0)走到(x, y)最短路径就是曼哈顿距离。如果这个最短距离都超过了2020那肯定无法在2020步内到达。因此问题瞬间简化了我们不需要模拟过程只需要枚举一个有限区域内的所有整数点然后判断这个点是否至少与一个初始感染点的曼哈顿距离 2020。如果是则该点被感染。接下来的关键就是这个需要枚举的“有限区域”有多大我们不能枚举无限平面但我们可以确定一个边界框。由于初始点坐标是(0,0), (2020,11), (11,14), (2000,2000)扩散范围是2020那么所有可能被感染的点其坐标一定满足min_x - 2020 x max_x 2020min_y - 2020 y max_y 2020其中min_x, max_x是四个初始点x坐标的最小最大值y坐标同理。计算一下x坐标最小是0最大是2000y坐标最小是0最大是2000。所以枚举范围大约是x ∈ [-2020, 4020],y ∈ [-2020, 4020]。这个区域大约是6000*60003600万个点。对于每个点我们需要计算它与4个初始点的曼哈顿距离。3600万 * 4 约1.44亿次距离计算。每次计算就是两次绝对值加法这是一个常数级别的操作。在C中1.44亿次简单运算是完全可以在1秒内完成的通常现代CPU每秒可进行数十亿次运算。因此枚举判断法是此题的可行且高效的解决方案。2. 曼哈顿距离与BFS算法的本质联系在深入代码之前我们有必要厘清曼哈顿距离判断法和BFS模拟法之间的深层联系。这能帮助我们理解为什么前者能替代后者以及在什么情况下它们等价。BFS广度优先搜索模拟是从源点一层层向外“涟漪式”地探索。在第0分钟只有初始点。第1分钟是所有初始点的曼哈顿距离为1的点。第2分钟是所有曼哈顿距离为2的点且未被之前感染的点…… 以此类推。BFS天然地按照曼哈顿距离的层次来遍历节点。在无障碍物的无限网格上本题正是如此从单源点(x0, y0)进行BFS第t分钟或第t步访问到的所有新节点恰好就是所有满足曼哈顿距离 t的节点。而t分钟内能访问到的所有节点的集合就是所有满足曼哈顿距离 t的节点。这是一个非常重要的性质。它意味着在这种理想网格上BFS的“前沿”就是一个以源点为中心的菱形或者说旋转了45度的正方形。这个菱形上的所有点到源点的曼哈顿距离相等。对于多源点BFS本题有4个初始感染点情况类似。任何一个点(x, y)只要它到任意一个源点的曼哈顿距离 t那么它一定会在t分钟内被感染。因为多源BFS可以看作是同时从多个源点开始的BFS每个点被感染的时间等于它到所有源点的曼哈顿距离的最小值。因此min_distance_to_any_source(x, y) 2020这个判断条件完全等价于对这个多点系统进行2020分钟的BFS模拟后该点是否被访问到的结果。这就是我们能用数学计算替代模拟过程的理论基础。思考如果题目中的扩散规则变了比如每分钟可以走“斜角”像国际象棋里的国王那么最短距离就变成了切比雪夫距离max(|x-x0|, |y-y0|)。判断条件也要相应改变。所以理解“距离”的定义如何由“移动规则”决定是解决这类扩散/传播问题的关键。3. 从暴力枚举到代码实现理论清晰了现在我们来动手实现。我们将采用最直接的枚举判断法。代码结构非常清晰定义初始点将四个初始感染点存入一个数组或向量。确定枚举边界计算所有初始点x和y坐标的最大最小值然后分别减去和加上扩散时间2020得到我们要枚举的x和y的范围。双重循环枚举遍历边界范围内的每一个整数坐标(i, j)。判断感染对于每个(i, j)计算它到四个初始点的曼哈顿距离。如果有一个距离 2020则计数器加1。输出结果循环结束后计数器中的值就是答案。这里有一个极其重要的细节初始的四个点本身在第0分钟就已经被感染了。在我们的判断条件距离 2020中它们到自身的距离是0显然满足条件所以会被自然计数在内。我们不需要单独处理。让我们来看核心代码实现#include iostream #include vector #include cmath // 用于abs函数但也可以自己实现 using namespace std; // 定义点的结构体 struct Point { int x, y; Point(int _x, int _y) : x(_x), y(_y) {} }; int main() { // 1. 初始化四个源点 vectorPoint sources; sources.emplace_back(0, 0); sources.emplace_back(2020, 11); sources.emplace_back(11, 14); sources.emplace_back(2000, 2000); int time_limit 2020; int cnt 0; // 感染点计数器 // 2. 计算枚举的边界 int min_x 0, max_x 2000; // 已知的初始点坐标范围 int min_y 0, max_y 2000; // 实际上我们需要根据初始点动态计算这里直接写出已知值。更通用的写法是遍历sources数组求最值。 // int min_x sources[0].x, max_x sources[0].x; // int min_y sources[0].y, max_y sources[0].y; // for (const auto p : sources) { // min_x min(min_x, p.x); max_x max(max_x, p.x); // min_y min(min_y, p.y); max_y max(max_y, p.y); // } int start_x min_x - time_limit; int end_x max_x time_limit; int start_y min_y - time_limit; int end_y max_y time_limit; // 3. 双重循环枚举所有点 for (int x start_x; x end_x; x) { for (int y start_y; y end_y; y) { // 4. 判断当前点(x,y)是否能在time_limit内被任一源点感染 bool infected false; for (const auto source : sources) { int distance abs(x - source.x) abs(y - source.y); if (distance time_limit) { infected true; break; // 找到一个可达源点就跳出内层循环 } } if (infected) { cnt; } } } // 5. 输出结果 cout cnt endl; return 0; }这段代码逻辑正确但我们可以做一些优化和补充说明边界计算代码中我注释掉了动态计算边界的部分直接用了已知值。在正式解题时建议使用动态计算这样即使初始点改变代码也无需修改。abs()函数计算曼哈顿距离需要用到绝对值。cmath或cstdlib中的abs()函数对整数是有效的。也可以自己写一个int d (x source.x) ? (x - source.x) : (source.x - x);但使用标准库函数更简洁。循环优化对于最内层循环要判断4个源点我们采用了break提前退出。这是一个小的优化。因为一旦发现某个点可达就没必要再计算它到其他源点的距离了。时间复杂度如前所述枚举点数量约(40002020*2)^2 ≈ 6000^2 36M每个点最多4次距离计算总共约1.44亿次操作在竞赛的1秒/2秒时限内是可行的。运行这段代码你会得到最终的答案。这里我不直接写出答案希望你能够自己运行并验证。4. 算法优化与边界情况探讨虽然枚举法已经可以解决问题但我们还可以思考一下有无优化空间以及一些特殊的边界情况。优化思路减少枚举量我们枚举了一个矩形区域但实际感染点分布在一个类似“四个菱形并集”的形状里。矩形的四个角有很大一片区域是绝对不可能被感染的距离所有源点都太远。有没有办法只枚举可能的区域呢一个思路是对于每个源点感染区域是一个菱形。我们可以枚举每个源点对应的菱形区域然后取这些区域的并集。但计算并集本身比较麻烦可能需要使用扫描线或者更复杂的几何计算其编程复杂度远高于简单的矩形枚举。在竞赛中“矩形枚举距离判断”在实现速度和思维难度上取得了最佳平衡是最推荐的做法。另一种思路是只枚举y轴方向然后对于每个y计算x的取值范围。因为对于一个给定的y到某个固定源点(x0, y0)曼哈顿距离 T的点其x坐标必须满足|x - x0| T - |y - y0|。即x0 - (T - |y-y0|) x x0 (T - |y-y0|)。对于多个源点x的取值范围就是这些区间的并集。我们可以遍历y然后计算每个y对应的x区间并集的总长度最后求和。这种方法可以将复杂度从O(N^2)降到O(N * K)其中N是坐标范围K是源点数量这里K4。实现起来比双重循环稍复杂但效率更高。不过对于本题规模双重循环足矣。边界情况与易错点坐标范围与整数溢出本题坐标和扩散时间都在2000左右加减后范围在-2020到4020之间用int类型完全足够不会溢出。时间从0开始第0分钟已经有4个点。我们的算法中距离2020的点包含了第0到第2020分钟所有被感染的点计算是正确的。如果题目问“第2020分钟结束后”或者“经过2020分钟后”通常都包括初始状态。源点重复题目保证了源点不重复。如果源点重复我们的算法依然正确因为重复判断并不会增加计数一个点不会被重复感染。答案的表示最终答案是一个整数可能比较大百万级别用int或long long存储均可。踩坑实录我最初实现时曾想当然地认为感染区域是一个大矩形于是尝试计算矩形面积。但很快发现四个菱形区域的并集并不是一个简单的矩形它的边界是凹凸不平的。直接计算面积会漏掉一些凹进去的格子也会多算一些凸出来的角。这个错误让我意识到在离散网格上基于曼哈顿距离的形状其面积不能直接用连续几何的公式计算必须通过离散点的枚举来精确计数。这是此类题目一个经典的思维陷阱。5. 从“扩散”到更广泛的搜索问题解决这道“扩散”题我们掌握的核心武器是将BFS的“过程模拟”问题转化为基于“距离”的“状态判断”问题。这个思想可以推广到许多类似场景多源点BFS最短路径在一个无权图中或网格中求所有点到一组起点的最近距离。可以直接初始化所有起点距离为0然后一次性放入队列进行BFS。这本质上就是多源扩散。障碍物环境如果网格中存在障碍物曼哈顿距离的最短路径性质就被破坏了。因为两点之间的直线路径可能被挡住。此时就必须老老实实进行BFS或Dijkstra算法如果边权不同来模拟。本题没有障碍物是简化情况的关键。不同距离度量如果扩散规则是八方向米字型则使用切比雪夫距离如果是在三维空间曼哈顿距离定义为|dx||dy||dz|。规则决定距离度量。时间作为距离在这类每分钟扩散一格的题目中“时间”和“最短路径长度”是等价的。这启发我们在一些问题中可以把时间维度转化为图论中的路径长度来思考。理解了这个本质后你再看到类似的“扩散”、“感染”、“传播”问题首先应该问自己移动规则是什么有没有障碍如果移动规则简单如四方向/八方向且没有障碍那么很可能可以绕过模拟直接用距离公式进行高效计算。如果规则复杂或有障碍那么BFS/DFS模拟就是唯一可靠的方法。最后关于这道题的答案我强烈建议你根据上面的思路自己动手编写代码运行并得出结果。编程竞赛的魅力就在于思考和实现的过程。如果你在实现中遇到任何问题比如边界条件没处理好导致答案差了几个或者循环写错了那正是加深理解的好机会。调试的过程就是对你思维严密性的一次最好训练。