1. 从“扩散”到“连通”一道蓝桥杯国赛题的解题思维跃迁如果你参加过蓝桥杯或者对算法竞赛稍有了解那么“扩散”这个题目名称可能会让你联想到物理过程、图论模型甚至是深度学习里的扩散模型。但第十一届蓝桥杯国赛的这道“扩散”题却是一个经典的、披着“模拟”外衣的“BFS连通性”问题。它考察的核心远不止是简单的模拟而是对问题本质的抽象能力、对算法复杂度的把控以及对边界条件的细致处理。很多选手初次接触时容易陷入无脑模拟的陷阱导致程序在有限时间内无法得出结果或者因为内存爆炸而崩溃。今天我们就来彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及“如何想到这么做”。这道题描述了一个在无限大网格上的“感染”过程初始时刻第0分钟在平面上的某些特定坐标点存在一个“黑点”。此后每一分钟每个已有的黑点会向其上、下、左、右四个相邻的网格点扩散一个新的黑点。题目最终问的是在第2020分钟注意这是一个关键参数时平面上有多少个黑点。初看之下这似乎就是一个标准的模拟题维护一个集合表示黑点每分钟遍历所有黑点向四周扩散循环2020次即可。但如果你真这么写迎接你的很可能是“运行超时”甚至“内存超限”。为什么因为黑点的数量是指数级增长的。我们需要换一种思维。2. 问题重述与核心矛盾为什么不能暴力模拟让我们先把题目用更严谨的语言描述一遍并立刻指出暴力模拟的不可行性。问题重述 在一个二维无限大的整数坐标网格中初始时刻t0在若干个坐标点上有“黑点”。对于任意时刻 t (t 0)如果一个坐标点 (x, y) 在时刻 t 是黑点那么在时刻 t1其四个邻居点 (x1, y), (x-1, y), (x, y1), (x, y-1) 也会变成黑点如果之前不是则新增如果之前已经是则保持不变。给定初始黑点坐标求在 t 2020 时网格中黑点的总数。暴力模拟的复杂度分析 假设初始有 k 个点。第0分钟有 k 个点。 第1分钟每个初始点产生4个新点但可能与其它点扩散的重合最坏情况下点数变为 k 4k 5k。 第2分钟每个现有的5k个点又尝试向四周扩散点数将进一步爆炸式增长。 经过 t 分钟后理论上可达的点构成了以每个初始点为中心、曼哈顿距离|dx||dy|不超过 t 的所有整数点的并集。这个点的数量级是 O(t²) 乘以初始点数 k。对于 t2020这个集合的大小是百万甚至千万级别的。如果使用一个大的二维数组来标记考虑到坐标可能为负我们需要进行坐标偏移数组大小会非常惊人。如果使用 HashSet 之类的数据结构存储每个点的坐标每次扩散都需要遍历当前所有点并插入新点2020轮循环的耗时将是不可接受的尤其是在竞赛环境下通常1秒的时间限制。因此核心矛盾在于扩散过程是“并行”的所有点同时影响其邻居。我们不需要模拟每一分钟的动态过程只需要判断在 t2020 这一刻一个点有没有可能被“感染”到。思维转换 一个点 (x, y) 在时刻 T 成为黑点的充要条件是存在一个初始点 (x0, y0)使得从 (x0, y0) 到 (x, y) 的曼哈顿距离|x - x0| |y - y0| T。 因为每分钟只能向相邻点移动一步扩散一步所以从一个初始点“扩散”到目标点所需的最短时间就是两者间的曼哈顿距离。只要这个距离小于等于给定的时间 T那么该目标点最晚在时刻 T 一定能被该初始点覆盖。于是问题转化为给定平面上若干个初始点源点求在曼哈顿距离度量下所有到任意一个源点的距离不超过 T2020 的整数点 (x, y) 的个数。这是一个计算几何中的离散点集可达区域问题更具体地说是求多个菱形曼哈顿距离下的“圆”的并集所覆盖的整数点个数。3. 算法核心曼哈顿距离与区域并集计算既然我们知道了判断单个点是否被覆盖的方法那么最直接的思路就是枚举所有可能被覆盖的点的范围对每个点用上面的条件判断。但枚举的范围是多大呢确定枚举边界 假设初始点中x 坐标的最小值是 min_x最大值是 max_xy 坐标的最小值是 min_y最大值是 max_y。 由于扩散范围是曼哈顿距离 T所以最终被覆盖的点的 x 坐标一定在[min_x - T, max_x T]之间y 坐标一定在[min_y - T, max_y T]之间。 这是一个矩形区域。我们只需要枚举这个矩形区域内的所有整数点即可。对于本题题目给出的初始点坐标是固定的这是蓝桥杯题目的特点通常样例或最终测试数据是固定的。我们假设初始点坐标为(0,0), (2020, 11), (11, 14), (2000, 2000)。实际上原题给出的就是这四个点。那么min_x 0, max_x 2020min_y 0, max_y 2000T 2020所以 x 的枚举范围是[0 - 2020, 2020 2020][-2020, 4040]总宽度是 6061。 y 的枚举范围是[0 - 2020, 2000 2020][-2020, 4020]总高度是 6041。 需要枚举的总点数约为 6061 * 6041 ≈ 36,600,000 个点即三千六百万个点。对于每个点我们需要计算它到4个初始点的曼哈顿距离并判断最小值是否 2020。这大约是 3.6千万 * 4 ≈ 1.44亿次距离计算。每次计算是两次绝对值加减法运算量不大。在 C 或 Java 等语言中这样的双重循环在优化良好的情况下是可以在1秒内完成的。这构成了本题的基础解法。基础解法伪代码输入初始点集合 sources {(x1,y1), (x2,y2), ...}, T2020 计算 min_x, max_x, min_y, max_y count 0 for x from min_x - T to max_x T: for y from min_y - T to max_y T: for each (sx, sy) in sources: if abs(x - sx) abs(y - sy) T: count break // 只要被一个源点覆盖即可 输出 count这个解法逻辑清晰易于实现对于本题的数据规模是可行的。它本质上是一种基于枚举和距离判断的填充算法。4. 优化与进阶思考从枚举到“膨胀”虽然基础枚举法已经可以解题但我们不妨再深入思考有没有更“优雅”或更“算法化”的解法这能帮助我们应对数据范围更大的变种题。方法二BFS广度优先搜索这可能是最符合“扩散”直觉的算法。我们把每个初始点放入队列并标记其距离为0。然后进行BFS每次从队列取出一个点如果其距离d T则将其四个邻居若未访问过加入队列距离标记为d1。最终所有被访问到的点的数量就是答案。优点直观完全模拟了扩散过程但避免了重复判断和指数级增长。它只计算了最终状态下的点而不是中间所有时刻的点。复杂度访问的点数就是最终答案的数量大约是 O(k * T²) 量级。对于本题答案本身就在千万级别所以BFS需要访问所有答案点每个点访问一次每个点会扩展4个邻居但很多会被剪枝。实际运行效率与枚举法相近但需要维护一个队列和一个巨大的访问标记集合同样需要处理负坐标通常用unordered_set或map存储坐标。注意事项BFS中同一个点可能被多个初始点以相同或不同的距离发现。我们需要记录每个点被访问时的最小距离只有当新距离小于等于T且小于已记录的最小距离时才需要将其加入队列进行后续扩散。否则一个点可能被重复加入队列多次造成冗余计算。这增加了逻辑复杂度。方法三计算几何方法求菱形并集这是理论上更优美的方法。每个初始点 (sx, sy) 在曼哈顿距离下覆盖的区域是一个中心在 (sx, sy)、“半径”为T的菱形或称倾斜45度的正方形。求多个菱形的并集覆盖的整数点个数。 一个菱形可以表示为|x - sx| |y - sy| T。 这等价于四个线性不等式的交集x - sx y - sy T-x y T sx syx - sx - (y - sy) T-x - y T sx - sy-(x - sx) y - sy T--x y T - sx sy-(x - sx) - (y - sy) T--x - y T - sx - sy求多个这样的凸多边形菱形的并集并计算其中整数点的数量可以使用扫描线算法配合区间合并但实现起来非常复杂在竞赛中性价比不高。不过这种思路揭示了问题的本质。为什么枚举法在本题足够好因为本题的 T (2020) 和坐标范围相对适中使得枚举的矩形区域大小在数千万量级现代计算机可以在1秒左右完成。蓝桥杯的评测机性能足以支撑。所以在竞赛中实现简单、不易出错的枚举法往往是首选。注意在编写代码时务必注意坐标偏移。如果你用数组visited[6061][6041]来标记需要将实际坐标 (x, y) 映射到数组下标(x 2020, y 2020)确保下标非负。5. 代码实现与细节剖析C示例下面给出基于枚举法的C详细实现并逐段分析关键细节。#include iostream #include cmath using namespace std; // 初始点坐标根据题目给出 struct Point { int x, y; } sources[4] { {0, 0}, {2020, 11}, {11, 14}, {2000, 2000} }; const int T 2020; int main() { // 1. 计算枚举的边界 int min_x sources[0].x, max_x sources[0].x; int min_y sources[0].y, max_y sources[0].y; for (int i 1; i 4; i) { min_x min(min_x, sources[i].x); max_x max(max_x, sources[i].x); min_y min(min_y, sources[i].y); max_y max(max_y, sources[i].y); } int left min_x - T; int right max_x T; int bottom min_y - T; int top max_y T; // 2. 枚举矩形区域内的每一个点 long long count 0; // 结果可能很大用long long for (int x left; x right; x) { for (int y bottom; y top; y) { // 3. 检查当前点是否被任意初始点覆盖 for (int i 0; i 4; i) { int distance abs(x - sources[i].x) abs(y - sources[i].y); if (distance T) { count; break; // 只要被一个点覆盖就跳出内层循环 } } } } cout count endl; return 0; }关键细节剖析边界计算第12-19行。这里计算了初始点的最小外包矩形然后向四周扩展T得到枚举边界。这是最稳妥的方式确保不会漏掉任何可能被覆盖的点。一个常见的错误是直接枚举一个以原点为中心、足够大的正方形虽然可能也能覆盖但不够精确可能浪费计算时间或意外遗漏如果初始点非常偏。循环变量类型与结果类型第24行count使用了long long。这是非常重要的。因为最终答案可能很大本题答案是一个七位数用int可能会溢出。养成习惯在不能确定范围时对于计数变量使用long long。曼哈顿距离计算第29行abs(x - sources[i].x) abs(y - sources[i].y)。注意使用标准库的abs()函数它对于整数参数是有效的。确保包含了cmath或cstdlib头文件。剪枝第30-34行的break语句。一旦发现当前点 (x, y) 被某个初始点覆盖就立即停止检查其他初始点。因为题目只关心“是否被覆盖”而不关心被几个点覆盖。这个break能节省大约25%的计算量假设覆盖区域有大量重叠。性能估算我们之前估算枚举点数为 6061 * 6041 ≈ 36.6M。对于每个点最坏检查4次距离计算约4次减法、2次绝对值、1次加法、1次比较。按现代CPU每秒数十亿次运算的能力这个计算量是完全可以接受的。在实际测试中这段代码的运行时间远小于1秒。6. 从解题到举一反三题型总结与变式探讨解决一道题的价值在于掌握一类题的方法。“扩散”这道题为我们提供了一个很好的模型。核心模型多源点曼哈顿距离可达区域问题。特征在网格图上多个源点同时开始每步向四邻域扩散求经过T时间后被覆盖的格子总数。关键转化将动态模拟过程转化为静态距离判断。点 (x,y) 在 T 时刻被覆盖 存在源点 (sx,sy) 使得曼哈顿距离|x-sx||y-sy| T。通用解法枚举法确定包围盒[min_x-T, max_xT]x[min_y-T, max_yT]枚举其中所有点并用距离判断。适用于 T 和坐标范围适中使得枚举点数量在可接受范围例如数千万以内。BFS法从所有源点同时开始BFS记录每个点被访问到的最短时间距离只将距离 T 的点继续扩散。适用于需要精确知道每个点被覆盖的时间或者当 T 很大但实际覆盖区域相对稀疏时。公式法/几何法理论求多个菱形的并集面积整数点个数。实现复杂竞赛中少见。常见变式与应对策略扩散规则变化如果不是四方向而是八方向国王移动那么距离度量就变成了切比雪夫距离max(|x-sx|, |y-sy|)。判断条件相应改变。如果是六边形网格则需要使用六边形坐标系下的距离公式。带权扩散/速度不同如果每个源点的扩散速度不同例如有的点每分钟扩散1格有的扩散2格那么判断条件变为|x-sx||y-sy| v_i * T其中v_i是源点 i 的速度。算法框架不变只是距离计算时比较的阈值因源点而异。求恰好第 T 时刻新增的点这需要动态计算。可以计算 T 时刻覆盖的点集再减去 T-1 时刻覆盖的点集。而 T-1 时刻的点集可以用同样的方法将 T 替换为 T-1得到。注意这要求我们能高效计算覆盖点集如果枚举法可行则分别计算两次做差即可。无限网格与坐标偏移本题网格是无限的坐标可以为负。在代码中如果用数组存储访问标记坐标偏移是必须的。一个稳健的做法是先计算出枚举的边界left, right, bottom, top然后用二维数组vis时将点(x, y)映射到(x - left, y - bottom)。这样能保证下标从0开始且数组大小刚好是(right-left1) * (top-bottom1)。大数据范围下的优化如果 T 非常大例如 10^9枚举法显然不行。此时需要考虑数学方法。观察曼哈顿距离的菱形其覆盖的整数点个数有一个公式对于单个源点边长为 T 的菱形曼哈顿距离下的“圆”内的整数点个数为1 2*T*(T1)。但是多个菱形并集的点数计算就非常复杂涉及到容斥原理且菱形相交部分的形状可能是复杂的凸多边形。这通常是更高级的竞赛或学术问题。7. 竞赛实战中的技巧与避坑指南基于这道“扩散”题我总结了一些在蓝桥杯及类似算法竞赛中处理此类问题的实战技巧。技巧一先估算再编码在动手前一定要对数据规模和算法复杂度进行估算。像本题看到 T2020就要立刻意识到暴力模拟分钟是行不通的指数爆炸而枚举所有可能点千万级别是可行的。估算枚举点数(max_x - min_x 2*T) * (max_y - min_y 2*T)。如果这个数超过 10^8就要谨慎考虑枚举法了。技巧二利用对称性与周期性如果存在有些扩散问题在无限网格上具有对称性。例如如果初始点只有一个且位于原点那么覆盖区域是一个完美的菱形点数公式为1 2*T*(T1)。如果初始点分布有规律如都在一条直线上可能可以通过计算等差数列和来简化。本题初始点无规律所以老实用通用方法。技巧三调试时使用小数据在编写和调试代码时先将 T 设置为一个很小的值比如 2 或 3手动计算出结果然后用你的程序跑看结果是否一致。这是验证算法逻辑正确性的最快方法。确保小数据正确后再替换成最终的 T2020。避坑指南坑1整数溢出。计数变量用int导致结果错误。务必使用long long。坑2边界计算错误。枚举范围[min_x - T, max_x T]注意是闭区间。循环时x right不要写成x right。坑3abs() 函数使用。对于整数使用 C 标准库的abs()它在cstdlib或cmath中。如果自己实现要确保处理负数。坑4BFS中的重复访问。如果采用BFS一定要用一个数组或集合记录每个点是否已入队或者记录其最短距离避免同一点多次入队导致死循环或超时。坑5坐标映射错误。如果使用二维数组做标记计算下标时idx_x x - leftidx_y y - bottom。确保left和bottom是枚举的最小 x 和 y。最后这道“扩散”题在第十一届国赛中出现其难度定位在中等。它完美地考察了选手的问题转化能力。竞赛中很多题目都不是直接套用模板而是需要你剥开描述的外壳看到其本质的数学模型。看到“每一分钟向四周扩散”要能立刻联想到“曼哈顿距离”和“BFS”看到无限大网格和固定时间要能想到从动态模拟转化为静态判定。这种思维能力的训练远比记住某个具体算法的代码更重要。
蓝桥杯国赛题解：从扩散模拟到曼哈顿距离的算法思维跃迁
1. 从“扩散”到“连通”一道蓝桥杯国赛题的解题思维跃迁如果你参加过蓝桥杯或者对算法竞赛稍有了解那么“扩散”这个题目名称可能会让你联想到物理过程、图论模型甚至是深度学习里的扩散模型。但第十一届蓝桥杯国赛的这道“扩散”题却是一个经典的、披着“模拟”外衣的“BFS连通性”问题。它考察的核心远不止是简单的模拟而是对问题本质的抽象能力、对算法复杂度的把控以及对边界条件的细致处理。很多选手初次接触时容易陷入无脑模拟的陷阱导致程序在有限时间内无法得出结果或者因为内存爆炸而崩溃。今天我们就来彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及“如何想到这么做”。这道题描述了一个在无限大网格上的“感染”过程初始时刻第0分钟在平面上的某些特定坐标点存在一个“黑点”。此后每一分钟每个已有的黑点会向其上、下、左、右四个相邻的网格点扩散一个新的黑点。题目最终问的是在第2020分钟注意这是一个关键参数时平面上有多少个黑点。初看之下这似乎就是一个标准的模拟题维护一个集合表示黑点每分钟遍历所有黑点向四周扩散循环2020次即可。但如果你真这么写迎接你的很可能是“运行超时”甚至“内存超限”。为什么因为黑点的数量是指数级增长的。我们需要换一种思维。2. 问题重述与核心矛盾为什么不能暴力模拟让我们先把题目用更严谨的语言描述一遍并立刻指出暴力模拟的不可行性。问题重述 在一个二维无限大的整数坐标网格中初始时刻t0在若干个坐标点上有“黑点”。对于任意时刻 t (t 0)如果一个坐标点 (x, y) 在时刻 t 是黑点那么在时刻 t1其四个邻居点 (x1, y), (x-1, y), (x, y1), (x, y-1) 也会变成黑点如果之前不是则新增如果之前已经是则保持不变。给定初始黑点坐标求在 t 2020 时网格中黑点的总数。暴力模拟的复杂度分析 假设初始有 k 个点。第0分钟有 k 个点。 第1分钟每个初始点产生4个新点但可能与其它点扩散的重合最坏情况下点数变为 k 4k 5k。 第2分钟每个现有的5k个点又尝试向四周扩散点数将进一步爆炸式增长。 经过 t 分钟后理论上可达的点构成了以每个初始点为中心、曼哈顿距离|dx||dy|不超过 t 的所有整数点的并集。这个点的数量级是 O(t²) 乘以初始点数 k。对于 t2020这个集合的大小是百万甚至千万级别的。如果使用一个大的二维数组来标记考虑到坐标可能为负我们需要进行坐标偏移数组大小会非常惊人。如果使用 HashSet 之类的数据结构存储每个点的坐标每次扩散都需要遍历当前所有点并插入新点2020轮循环的耗时将是不可接受的尤其是在竞赛环境下通常1秒的时间限制。因此核心矛盾在于扩散过程是“并行”的所有点同时影响其邻居。我们不需要模拟每一分钟的动态过程只需要判断在 t2020 这一刻一个点有没有可能被“感染”到。思维转换 一个点 (x, y) 在时刻 T 成为黑点的充要条件是存在一个初始点 (x0, y0)使得从 (x0, y0) 到 (x, y) 的曼哈顿距离|x - x0| |y - y0| T。 因为每分钟只能向相邻点移动一步扩散一步所以从一个初始点“扩散”到目标点所需的最短时间就是两者间的曼哈顿距离。只要这个距离小于等于给定的时间 T那么该目标点最晚在时刻 T 一定能被该初始点覆盖。于是问题转化为给定平面上若干个初始点源点求在曼哈顿距离度量下所有到任意一个源点的距离不超过 T2020 的整数点 (x, y) 的个数。这是一个计算几何中的离散点集可达区域问题更具体地说是求多个菱形曼哈顿距离下的“圆”的并集所覆盖的整数点个数。3. 算法核心曼哈顿距离与区域并集计算既然我们知道了判断单个点是否被覆盖的方法那么最直接的思路就是枚举所有可能被覆盖的点的范围对每个点用上面的条件判断。但枚举的范围是多大呢确定枚举边界 假设初始点中x 坐标的最小值是 min_x最大值是 max_xy 坐标的最小值是 min_y最大值是 max_y。 由于扩散范围是曼哈顿距离 T所以最终被覆盖的点的 x 坐标一定在[min_x - T, max_x T]之间y 坐标一定在[min_y - T, max_y T]之间。 这是一个矩形区域。我们只需要枚举这个矩形区域内的所有整数点即可。对于本题题目给出的初始点坐标是固定的这是蓝桥杯题目的特点通常样例或最终测试数据是固定的。我们假设初始点坐标为(0,0), (2020, 11), (11, 14), (2000, 2000)。实际上原题给出的就是这四个点。那么min_x 0, max_x 2020min_y 0, max_y 2000T 2020所以 x 的枚举范围是[0 - 2020, 2020 2020][-2020, 4040]总宽度是 6061。 y 的枚举范围是[0 - 2020, 2000 2020][-2020, 4020]总高度是 6041。 需要枚举的总点数约为 6061 * 6041 ≈ 36,600,000 个点即三千六百万个点。对于每个点我们需要计算它到4个初始点的曼哈顿距离并判断最小值是否 2020。这大约是 3.6千万 * 4 ≈ 1.44亿次距离计算。每次计算是两次绝对值加减法运算量不大。在 C 或 Java 等语言中这样的双重循环在优化良好的情况下是可以在1秒内完成的。这构成了本题的基础解法。基础解法伪代码输入初始点集合 sources {(x1,y1), (x2,y2), ...}, T2020 计算 min_x, max_x, min_y, max_y count 0 for x from min_x - T to max_x T: for y from min_y - T to max_y T: for each (sx, sy) in sources: if abs(x - sx) abs(y - sy) T: count break // 只要被一个源点覆盖即可 输出 count这个解法逻辑清晰易于实现对于本题的数据规模是可行的。它本质上是一种基于枚举和距离判断的填充算法。4. 优化与进阶思考从枚举到“膨胀”虽然基础枚举法已经可以解题但我们不妨再深入思考有没有更“优雅”或更“算法化”的解法这能帮助我们应对数据范围更大的变种题。方法二BFS广度优先搜索这可能是最符合“扩散”直觉的算法。我们把每个初始点放入队列并标记其距离为0。然后进行BFS每次从队列取出一个点如果其距离d T则将其四个邻居若未访问过加入队列距离标记为d1。最终所有被访问到的点的数量就是答案。优点直观完全模拟了扩散过程但避免了重复判断和指数级增长。它只计算了最终状态下的点而不是中间所有时刻的点。复杂度访问的点数就是最终答案的数量大约是 O(k * T²) 量级。对于本题答案本身就在千万级别所以BFS需要访问所有答案点每个点访问一次每个点会扩展4个邻居但很多会被剪枝。实际运行效率与枚举法相近但需要维护一个队列和一个巨大的访问标记集合同样需要处理负坐标通常用unordered_set或map存储坐标。注意事项BFS中同一个点可能被多个初始点以相同或不同的距离发现。我们需要记录每个点被访问时的最小距离只有当新距离小于等于T且小于已记录的最小距离时才需要将其加入队列进行后续扩散。否则一个点可能被重复加入队列多次造成冗余计算。这增加了逻辑复杂度。方法三计算几何方法求菱形并集这是理论上更优美的方法。每个初始点 (sx, sy) 在曼哈顿距离下覆盖的区域是一个中心在 (sx, sy)、“半径”为T的菱形或称倾斜45度的正方形。求多个菱形的并集覆盖的整数点个数。 一个菱形可以表示为|x - sx| |y - sy| T。 这等价于四个线性不等式的交集x - sx y - sy T-x y T sx syx - sx - (y - sy) T-x - y T sx - sy-(x - sx) y - sy T--x y T - sx sy-(x - sx) - (y - sy) T--x - y T - sx - sy求多个这样的凸多边形菱形的并集并计算其中整数点的数量可以使用扫描线算法配合区间合并但实现起来非常复杂在竞赛中性价比不高。不过这种思路揭示了问题的本质。为什么枚举法在本题足够好因为本题的 T (2020) 和坐标范围相对适中使得枚举的矩形区域大小在数千万量级现代计算机可以在1秒左右完成。蓝桥杯的评测机性能足以支撑。所以在竞赛中实现简单、不易出错的枚举法往往是首选。注意在编写代码时务必注意坐标偏移。如果你用数组visited[6061][6041]来标记需要将实际坐标 (x, y) 映射到数组下标(x 2020, y 2020)确保下标非负。5. 代码实现与细节剖析C示例下面给出基于枚举法的C详细实现并逐段分析关键细节。#include iostream #include cmath using namespace std; // 初始点坐标根据题目给出 struct Point { int x, y; } sources[4] { {0, 0}, {2020, 11}, {11, 14}, {2000, 2000} }; const int T 2020; int main() { // 1. 计算枚举的边界 int min_x sources[0].x, max_x sources[0].x; int min_y sources[0].y, max_y sources[0].y; for (int i 1; i 4; i) { min_x min(min_x, sources[i].x); max_x max(max_x, sources[i].x); min_y min(min_y, sources[i].y); max_y max(max_y, sources[i].y); } int left min_x - T; int right max_x T; int bottom min_y - T; int top max_y T; // 2. 枚举矩形区域内的每一个点 long long count 0; // 结果可能很大用long long for (int x left; x right; x) { for (int y bottom; y top; y) { // 3. 检查当前点是否被任意初始点覆盖 for (int i 0; i 4; i) { int distance abs(x - sources[i].x) abs(y - sources[i].y); if (distance T) { count; break; // 只要被一个点覆盖就跳出内层循环 } } } } cout count endl; return 0; }关键细节剖析边界计算第12-19行。这里计算了初始点的最小外包矩形然后向四周扩展T得到枚举边界。这是最稳妥的方式确保不会漏掉任何可能被覆盖的点。一个常见的错误是直接枚举一个以原点为中心、足够大的正方形虽然可能也能覆盖但不够精确可能浪费计算时间或意外遗漏如果初始点非常偏。循环变量类型与结果类型第24行count使用了long long。这是非常重要的。因为最终答案可能很大本题答案是一个七位数用int可能会溢出。养成习惯在不能确定范围时对于计数变量使用long long。曼哈顿距离计算第29行abs(x - sources[i].x) abs(y - sources[i].y)。注意使用标准库的abs()函数它对于整数参数是有效的。确保包含了cmath或cstdlib头文件。剪枝第30-34行的break语句。一旦发现当前点 (x, y) 被某个初始点覆盖就立即停止检查其他初始点。因为题目只关心“是否被覆盖”而不关心被几个点覆盖。这个break能节省大约25%的计算量假设覆盖区域有大量重叠。性能估算我们之前估算枚举点数为 6061 * 6041 ≈ 36.6M。对于每个点最坏检查4次距离计算约4次减法、2次绝对值、1次加法、1次比较。按现代CPU每秒数十亿次运算的能力这个计算量是完全可以接受的。在实际测试中这段代码的运行时间远小于1秒。6. 从解题到举一反三题型总结与变式探讨解决一道题的价值在于掌握一类题的方法。“扩散”这道题为我们提供了一个很好的模型。核心模型多源点曼哈顿距离可达区域问题。特征在网格图上多个源点同时开始每步向四邻域扩散求经过T时间后被覆盖的格子总数。关键转化将动态模拟过程转化为静态距离判断。点 (x,y) 在 T 时刻被覆盖 存在源点 (sx,sy) 使得曼哈顿距离|x-sx||y-sy| T。通用解法枚举法确定包围盒[min_x-T, max_xT]x[min_y-T, max_yT]枚举其中所有点并用距离判断。适用于 T 和坐标范围适中使得枚举点数量在可接受范围例如数千万以内。BFS法从所有源点同时开始BFS记录每个点被访问到的最短时间距离只将距离 T 的点继续扩散。适用于需要精确知道每个点被覆盖的时间或者当 T 很大但实际覆盖区域相对稀疏时。公式法/几何法理论求多个菱形的并集面积整数点个数。实现复杂竞赛中少见。常见变式与应对策略扩散规则变化如果不是四方向而是八方向国王移动那么距离度量就变成了切比雪夫距离max(|x-sx|, |y-sy|)。判断条件相应改变。如果是六边形网格则需要使用六边形坐标系下的距离公式。带权扩散/速度不同如果每个源点的扩散速度不同例如有的点每分钟扩散1格有的扩散2格那么判断条件变为|x-sx||y-sy| v_i * T其中v_i是源点 i 的速度。算法框架不变只是距离计算时比较的阈值因源点而异。求恰好第 T 时刻新增的点这需要动态计算。可以计算 T 时刻覆盖的点集再减去 T-1 时刻覆盖的点集。而 T-1 时刻的点集可以用同样的方法将 T 替换为 T-1得到。注意这要求我们能高效计算覆盖点集如果枚举法可行则分别计算两次做差即可。无限网格与坐标偏移本题网格是无限的坐标可以为负。在代码中如果用数组存储访问标记坐标偏移是必须的。一个稳健的做法是先计算出枚举的边界left, right, bottom, top然后用二维数组vis时将点(x, y)映射到(x - left, y - bottom)。这样能保证下标从0开始且数组大小刚好是(right-left1) * (top-bottom1)。大数据范围下的优化如果 T 非常大例如 10^9枚举法显然不行。此时需要考虑数学方法。观察曼哈顿距离的菱形其覆盖的整数点个数有一个公式对于单个源点边长为 T 的菱形曼哈顿距离下的“圆”内的整数点个数为1 2*T*(T1)。但是多个菱形并集的点数计算就非常复杂涉及到容斥原理且菱形相交部分的形状可能是复杂的凸多边形。这通常是更高级的竞赛或学术问题。7. 竞赛实战中的技巧与避坑指南基于这道“扩散”题我总结了一些在蓝桥杯及类似算法竞赛中处理此类问题的实战技巧。技巧一先估算再编码在动手前一定要对数据规模和算法复杂度进行估算。像本题看到 T2020就要立刻意识到暴力模拟分钟是行不通的指数爆炸而枚举所有可能点千万级别是可行的。估算枚举点数(max_x - min_x 2*T) * (max_y - min_y 2*T)。如果这个数超过 10^8就要谨慎考虑枚举法了。技巧二利用对称性与周期性如果存在有些扩散问题在无限网格上具有对称性。例如如果初始点只有一个且位于原点那么覆盖区域是一个完美的菱形点数公式为1 2*T*(T1)。如果初始点分布有规律如都在一条直线上可能可以通过计算等差数列和来简化。本题初始点无规律所以老实用通用方法。技巧三调试时使用小数据在编写和调试代码时先将 T 设置为一个很小的值比如 2 或 3手动计算出结果然后用你的程序跑看结果是否一致。这是验证算法逻辑正确性的最快方法。确保小数据正确后再替换成最终的 T2020。避坑指南坑1整数溢出。计数变量用int导致结果错误。务必使用long long。坑2边界计算错误。枚举范围[min_x - T, max_x T]注意是闭区间。循环时x right不要写成x right。坑3abs() 函数使用。对于整数使用 C 标准库的abs()它在cstdlib或cmath中。如果自己实现要确保处理负数。坑4BFS中的重复访问。如果采用BFS一定要用一个数组或集合记录每个点是否已入队或者记录其最短距离避免同一点多次入队导致死循环或超时。坑5坐标映射错误。如果使用二维数组做标记计算下标时idx_x x - leftidx_y y - bottom。确保left和bottom是枚举的最小 x 和 y。最后这道“扩散”题在第十一届国赛中出现其难度定位在中等。它完美地考察了选手的问题转化能力。竞赛中很多题目都不是直接套用模板而是需要你剥开描述的外壳看到其本质的数学模型。看到“每一分钟向四周扩散”要能立刻联想到“曼哈顿距离”和“BFS”看到无限大网格和固定时间要能想到从动态模拟转化为静态判定。这种思维能力的训练远比记住某个具体算法的代码更重要。