1. 问题重述与核心难点剖析“蓝桥杯2020年第十一届C/C国赛B组第二题-扩散”这道题乍一看题目描述可能很简单但真正动手做过的朋友都知道它是一道典型的“看起来简单做起来坑多”的题目。题目大意是在一个无限大的二维网格平面上初始时刻记为第0分钟有四个点被标记。从下一分钟开始每一个已被标记的点会将其上下左右四个相邻的网格点也标记上。这个过程每分钟发生一次问在第2020分钟时有多少个点被标记了。很多新手的第一反应是这不就是BFS广度优先搜索模拟吗开一个足够大的二维数组把四个初始点入队然后每分钟每次循环将队列中所有点的邻居入队并标记循环2020次最后统计被标记的点数。这个思路在逻辑上完全正确但如果你真这么写大概率会得到一个错误答案或者程序直接崩溃。这道题的“坑”就藏在这个“无限大”的平面和“2020分钟”这个看似不大的数字里。核心难点在于扩散的边界增长是线性的但被标记点的总数增长是平方级的。让我们来算一笔账初始只有4个点。每分钟每个点的“前沿”会向外推进一格。经过t分钟后从任何一个初始点扩散形成的图形大致是一个边长为(2t1)的菱形曼哈顿距离下的“圆”。四个点独立扩散最终覆盖的区域是这四个菱形的并集。直接模拟意味着我们需要维护一个覆盖了这个并集区域的二维数组。这个区域有多大呢最坏情况下四个初始点两两相距很远那么覆盖区域的长宽可能达到初始点最大坐标差 2 * 2020。题目没有给出初始坐标但根据常理和蓝桥杯一贯风格初始点坐标的绝对值可能在10以内。即便如此我们需要的数组大小也至少是(10 2020*2) * 2 ≈ 8100的边长。这看起来是一个8100x8100的数组似乎内存约65MB还能接受但这里还有第二个坑时间开销。模拟2020分钟每一分钟我们都要遍历当前所有已被标记的点这个数量在后期是百万级的并尝试标记其四个邻居。大量的重复判断一个点可能被多个邻居多次尝试标记和队列操作会导致程序运行极其缓慢甚至超时蓝桥杯通常有1秒的时间限制。所以这道题真正的考点不是“会不会BFS”而是“如何高效地计算离散点集在曼哈顿距离度量下的并集面积”。它引导我们跳出模拟的思维定式去寻找数学规律或更高效的算法模型。这也是国赛题目的典型风格考察选手的优化思维和模型转化能力。2. 从模拟到数学曼哈顿距离与菱形区域要高效解决这个问题我们必须放弃每分钟逐步模拟的想法转而从几何角度思考。题目中的扩散规则是一个点每分钟可以影响到其曼哈顿距离为1的点。那么在t分钟后一个初始点(x0, y0)能影响到哪些点呢答案是所有满足|x - x0| |y - y0| t的点(x, y)。这个不等式定义的区域在坐标系中就是一个以(x0, y0)为中心、倾斜45度的正方形也就是一个菱形。例如中心在(0,0)t2时覆盖的点包括(0,0), (0,±1), (0,±2), (±1,0), (±2,0), (±1, ±1)等。这个菱形区域内的所有整数坐标点都会被覆盖。因此原问题转化为给定平面上的四个点P1, P2, P3, P4求所有满足min( distance(P, P1), distance(P, P2), distance(P, P3), distance(P, P4) ) 2020的整数点P的个数其中distance是曼哈顿距离。这样一来我们就不需要模拟时间流逝了。我们只需要遍历一个包含了这四个菱形并集的矩形区域内的所有点判断每个点到四个初始点的最小曼哈顿距离是否小于等于2020即可。这依然是一个遍历但现在是单层遍历时间复杂度从模拟的O(T * N)N为过程中总点数降低到了O(W * H)其中W和H是遍历区域的长和宽。那么遍历区域应该取多大设四个初始点的横坐标最小值为min_x最大值为max_x纵坐标最小值为min_y最大值为max_y。由于最远的扩散距离是2020所以我们需要遍历的横坐标范围至少是[min_x - 2020, max_x 2020]纵坐标范围是[min_y - 2020, max_y 2020]。为了保险起见我们可以适当扩大这个范围确保完全覆盖。这种方法的计算量是多少假设初始点坐标在[-10, 10]之间那么遍历区域的边长大约是(10 - (-10)) 2*2020 4060。总点数约为4060 * 4060 ≈ 1648万。对于每个点我们需要计算其到4个点的曼哈顿距离并取最小值。总计算量约为1600万 * 4 6400万次曼哈顿距离计算。这在现代CPU上用C/C优化良好的循环来实现是完全可以在1秒内完成的。这就解决了模拟法超时的问题。3. 算法实现与关键细节基于上面的分析我们可以给出清晰的算法步骤和代码实现。这里假设题目给出的四个初始点坐标为(0,0), (2020,11), (11,14), (2000,2000)。实际上原题目的坐标是给定的我们需要用题目给定的数据。算法流程如下定义初始点将四个初始点的坐标存入数组。确定遍历边界找出四个点中x和y坐标的最大值(max_x,max_y)和最小值(min_x,min_y)。将边界向外扩展2020个单位得到遍历范围x从min_x - 2020到max_x 2020y从min_y - 2020到max_y 2020。遍历与判断使用双重循环遍历上述矩形区域内的每一个整数坐标点(i, j)。对于每个点计算它到四个初始点的曼哈顿距离。曼哈顿距离公式为abs(i - x_k) abs(j - y_k)。取这四个距离中的最小值。计数如果这个最小距离 2020则该点在2020分钟内可以被扩散到计数器加一。输出结果遍历结束后输出计数器的值。以下是具体的C实现代码#include iostream #include cmath // 用于abs函数 using namespace std; // 定义初始点坐标 (根据实际题目修改) struct Point { int x, y; } points[4] { {0, 0}, {2020, 11}, {11, 14}, {2000, 2000} }; int main() { // 1. 确定坐标范围 int min_x points[0].x, max_x points[0].x; int min_y points[0].y, max_y points[0].y; for (int i 1; i 4; i) { if (points[i].x min_x) min_x points[i].x; if (points[i].x max_x) max_x points[i].x; if (points[i].y min_y) min_y points[i].y; if (points[i].y max_y) max_y points[i].y; } // 2. 扩展遍历边界 int start_x min_x - 2020; int end_x max_x 2020; int start_y min_y - 2020; int end_y max_y 2020; // 3. 遍历与计数 int count 0; for (int i start_x; i end_x; i) { for (int j start_y; j end_y; j) { int min_dist 0x7fffffff; // 初始化为一个很大的数 for (int k 0; k 4; k) { int dist abs(i - points[k].x) abs(j - points[k].y); if (dist min_dist) { min_dist dist; } // 一个小优化如果发现距离已经2020可以提前结束内层k循环 // 但这里点集只有4个优化效果不明显保持逻辑清晰更重要。 } if (min_dist 2020) { count; } } } // 4. 输出结果 cout count endl; return 0; }关键细节与优化点边界确定务必确保遍历区域足够大要包含所有可能被覆盖的点。扩展距离 2020是理论最小值。如果初始点坐标的绝对值很大比如题目给了(10000, 10000)这样的点那么遍历区域会非常大边长超过22040计算量会激增到近5亿次距离计算可能面临超时风险。这时就需要考虑进一步的优化例如利用对称性或者使用基于队列但带有判重的BFS只扩展边界点。曼哈顿距离计算使用abs()函数计算绝对值这是最快的方式。循环优化在计算一个点到四个初始点的距离时如果某个距离已经小于等于2020那么该点肯定会被覆盖可以立即停止计算剩余初始点的距离直接计数。这是一个有效的剪枝。代码注释中提到了这一点。数据类型坐标和距离都用int足够计数器count可能需要long long但经过计算2020分钟四个点扩散的总点数不会超过(4041*4041)*4的理论最大值约6500万仍在int范围内约21亿所以用int即可。注意以上代码中的初始点坐标是示例你必须替换成题目中实际给出的坐标。蓝桥杯比赛时题目会明确给出这四个点的坐标。4. 深入思考算法优化与模型扩展虽然上述遍历方法已经可以解决本题但我们可以思考一下如果时间t变得非常大比如t10^9或者初始点变得非常多成千上万个我们该怎么办这时O(W*H)的遍历就不可行了。这引导我们进入计算几何中的一个经典问题计算多个曼哈顿距离“圆”菱形的并集所覆盖的整点数量。对于两个菱形的并集我们可以通过计算它们的交集也是一个菱形或多边形来容斥。但对于四个甚至更多容斥原理会变得非常复杂。一个更通用的方法是使用BFS/DFS 配合哈希表或集合进行判重。我们不再遍历整个矩形区域而是从四个初始点开始模拟扩散但使用unordered_set或pair映射到bool的哈希结构来存储已访问的点。每次从队列中取出一个点如果其“扩散时间”小于2020就将其四个邻居入队如果邻居未被访问过。这样我们只访问最终会被覆盖的那些点访问次数就是最终答案。这种方法在扩散范围即t远小于初始点分散程度时效率远高于全图遍历。BFS哈希表方法的伪代码思路#include iostream #include queue #include unordered_set using namespace std; struct Node { int x, y, step; // step表示从某个起点扩散到该点所需的时间 }; // 为pairint,int定义哈希函数用于unordered_set struct pair_hash { template class T1, class T2 std::size_t operator () (const std::pairT1,T2 p) const { auto h1 std::hashT1{}(p.first); auto h2 std::hashT2{}(p.second); return h1 ^ (h2 1); } }; int main() { // 初始点坐标 vectorpairint,int starts {{0,0}, {2020,11}, {11,14}, {2000,2000}}; queueNode q; unordered_setpairint,int, pair_hash visited; // 初始化队列和集合 for (auto p : starts) { q.push({p.first, p.second, 0}); visited.insert(p); } int directions[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; long long ans 0; while (!q.empty()) { Node cur q.front(); q.pop(); ans; // 每一个出队的点都是被覆盖的点 if (cur.step 2020) { continue; // 已经达到时间上限不再扩散 } for (int i 0; i 4; i) { int nx cur.x directions[i][0]; int ny cur.y directions[i][1]; pairint,int nxt_key {nx, ny}; if (visited.find(nxt_key) visited.end()) { visited.insert(nxt_key); q.push({nx, ny, cur.step 1}); } } } cout ans endl; return 0; }这种方法的空间复杂度取决于被覆盖的点数时间复杂度也是O(N)其中N是答案。在本题t2020且点较分散的情况下被覆盖的点数可能达到千万级使用哈希集合的内存开销和常数时间会比较大可能反而不如精心优化的数组遍历快。但它提供了一个更通用的思路。模型扩展这道题的扩散模型本质上是细胞自动机Conway‘s Game of Life的简化版和波前传播Wavefront Propagation的离散版本。在图像处理、模拟仿真、地图可达性分析等领域有广泛应用。例如计算火灾蔓延、病毒传播离散网格模型、广播信号覆盖范围等都可以抽象成类似的问题。理解曼哈顿距离下的区域增长是解决许多网格图最短路径和覆盖问题的基础。5. 常见错误与调试心得在解这道题时我见过也犯过不少错误这里总结一下帮你避坑数组越界与空间不足这是模拟法最容易出现的问题。如果你坚持用二维数组bool grid[N][N]来模拟必须精确估算N的大小。N至少需要等于(最大坐标 - 最小坐标) 2*t 1。并且数组要定义在全局区静态存储区因为栈空间通常只有几MB无法容纳这么大的数组。定义在全局区或动态分配vectorvectorbool是更安全的选择。时间计数错误在模拟法中容易混淆“第几分钟”和“经过了几分钟”。题目问的是“第2020分钟时”即从第0分钟开始经过了2020次扩散后。所以循环次数应该是2020次而不是2019次。在BFS中step或time字段表示的是从起点到当前点经过的分钟数当step 2020时该点本身是在第2020分钟被覆盖的但它不能再向外扩散了因为扩散发生在每分钟末。这个边界条件要理清。整数溢出在计算曼哈顿距离abs(i - x_k) abs(j - y_k)时i和x_k可能都是很大的整数如果初始坐标很大但它们的差以及和仍在int范围内。计数器count在本题数据规模下用int是安全的但养成使用long long的习惯更好尤其是当你不确定数据范围时。遍历范围不足这是数学方法的主要陷阱。如果你只遍历了[min_x, max_x]和[min_y, max_y]的范围那就大错特错了因为扩散会远远超出初始点的外包矩形。务必记得在四个方向上都扩展t个单位。忽略坐标偏移如果你使用数组模拟需要将所有的坐标平移使得最小坐标对应数组下标0以避免负索引。例如所有x坐标减去min_x - t所有y坐标减去min_y - t。在数学遍历法中直接使用原始坐标循环即可更简单。性能瓶颈在数学遍历法的三重循环中最内层是计算到4个点的距离。如果初始点很多比如本题是4个这个循环是常数时间没问题。但如果题目变成“成百上千个初始点”内层循环就会成为瓶颈。此时需要考虑空间换时间例如使用BFS哈希或者更高级的多源BFS所有起点同时初始化进队列距离时间为0然后统一进行BFS。多源BFS是解决这类“多个起点同时扩散”问题的最标准且高效的方法。调试建议先用小数据测试将时间t改为2或3用手工计算或在小网格上画出扩散过程验证你的程序输出是否正确。验证边界特意构造初始点坐标差很大、或者靠近理论计算边界的测试用例检查你的遍历范围是否足够。对比不同方法如果你写了模拟法和数学法用小的t测试确保两者结果一致。这能帮你发现逻辑错误。最后这道题给我的体会是竞赛编程中理解问题背后的数学模型往往比直接编写模拟代码更重要。它考察的是将实际问题抽象、转化并优化的能力。“扩散”问题从模拟到曼哈顿距离的转化是一个经典的思维提升过程。在平时练习时即使你用一种方法AC了也不妨思考一下是否有其他解法各种解法在什么数据规模下会失效又如何改进。这样刷一题才能真正收获一类题的经验。