1. 项目概述从“扩散”到“广度优先搜索”的思维跃迁“第十一届蓝桥杯CB组国赛试题B扩散”这个标题对于参加过蓝桥杯的选手来说瞬间就能勾起一系列回忆和思考。蓝桥杯作为国内覆盖面极广的大学生IT赛事其国赛题目往往代表着当届竞赛的最高难度和最新颖的思维考察点。这道“扩散”题正是这样一个典型。它初看可能让人联想到物理现象或数学模型但实际上它是一道经典的、披着“模拟”外衣的图论搜索问题核心考察的是选手对广度优先搜索BFS算法的深刻理解与灵活应用能力以及对坐标系处理和边界判断的编程基本功。这道题之所以令人印象深刻是因为它用一个非常生活化的概念——“扩散”包装了一个需要严谨算法逻辑才能高效解决的问题。题目通常会描述在一个无限的二维网格平面上有若干个初始点称为“黑点”在时刻0被“感染”。此后每一秒每个黑点会向上、下、左、右四个方向扩散一格将其相邻的网格也变为黑点。问题最终会问在某个特定的时刻T比如2020秒平面上有多少个网格点被染黑或者所有初始点形成的连通区域需要多少秒才能覆盖一个指定范围这种模型在计算机科学中无处不在例如网络传播模拟、图像处理中的区域生长、游戏中的地图探索战争迷雾等。解决它蛮力模拟在无限平面上是不可行的必须抓住“扩散”的波阵面是均匀推进的这一本质将其转化为从多个源点同时开始的BFS过程。BFS的“队列”天然地刻画了时间顺序队列中每一“层”的点就对应着某一秒新被扩散到的点。理解到这一步就从“模拟题”跨入了“算法题”的门槛。接下来我们将彻底拆解这道题不仅给出标准解法更会深入探讨其中的优化技巧、易错细节以及如何将这种思维迁移到其他相似场景中。2. 核心思路解析为什么BFS是唯一正解面对“扩散”问题新手最容易陷入的误区就是尝试直接模拟整个无限平面。他们会想开一个足够大的二维数组比如map[10000][10000]把初始点放进去然后循环T次每次遍历所有黑点并向四周扩散。这种方法在T很小、初始点很少时勉强可行但一旦T达到题目常见的上千量级无论时间还是空间复杂度都是灾难性的。时间复杂度是O(T * N * M)N、M为数组维度空间则是O(N*M)极易超时和内存超限。因此我们必须转换视角。关键洞察在于一个点被染黑的时刻等于它到任意一个初始点的最短曼哈顿距离。曼哈顿距离即两点在标准坐标系下横纵坐标差的绝对值之和。为什么因为扩散每次只能向四邻域移动一格所以从初始点“走”到目标点所需的最少步数时间就是曼哈顿距离。一个点可能被多个初始点扩散到它被染黑的时刻就是所有初始点中距离它最近的那个曼哈顿距离。于是问题转化为给定平面上若干个初始点对于平面上某个点或在某个范围内所有点求其到所有初始点的最小曼哈顿距离。如果问题是求T时刻有多少个点被覆盖那就是统计所有满足min_distance T的点数。那么如何高效计算呢这就是BFS登场的时候。BFS非常适合求解这种“从多个源点出发每一步代价相同”的最短路径问题。我们可以将所有初始点同时放入队列并标记其距离时间为0。然后进行标准的BFS每次从队列取出一个点检查其上下左右四个邻居。如果邻居未被访问过则其距离等于当前点距离1将其入队。这个过程会像水波一样一圈圈荡开当队列为空或者当我们扩展到足够的时间T时所有被访问到的点及其对应的“被感染时间”就都计算出来了。为什么不用深度优先搜索DFSDFS会一条路走到黑无法保证最先找到的解就是最短路径最小时间它求出的“距离”没有意义。而BFS按层推进的特性保证了第一次访问到某个节点时所用的步数一定是最少的。为什么不用直接计算曼哈顿距离对于“统计T时刻黑点数量”这类问题如果平面范围是无限的我们确实可以通过数学方法计算。例如一个初始点在第T秒后会形成一个中心在初始点、曼哈顿距离为T的菱形或称正方形旋转45度区域。多个初始点形成的区域会有重叠。计算多个菱形区域的并集面积涉及计算几何非常复杂且容易出错尤其是在需要处理整数格点的情况下。而BFS模拟扩散过程思路直观实现相对稳健是竞赛中的首选方法。注意BFS解法隐含了一个前提——平面在理论上是无限的但在计算机中我们必须设定一个搜索范围。这个范围需要根据初始点坐标和最大时间T来估算通常是[min_x - T, max_x T]和[min_y - T, max_y T]这个矩形区域。这是将无限问题有限化的关键一步也是容易出错的地方范围估小了会漏点估大了可能超时或超内存。3. 算法实现细节与关键步骤拆解理解了BFS是核心接下来我们深入到代码层面拆解每一个关键步骤。我将以C为例因为这是蓝桥杯CB组的比赛语言。我们会从数据结构选择、坐标处理、去重判断到完整代码框架一步步说明。3.1 数据结构设计与坐标映射在网格BFS中我们通常需要记录某个坐标点是否被访问过以及被访问时的时间距离。由于坐标可能是负数初始点可能在原点四周而C数组下标不能为负我们需要进行坐标映射。一种常见且安全的方法是使用std::unordered_set或std::set来存储已访问的点。我们可以将二维坐标编码成一个long long类型的整数。例如对于一个点(x, y)我们可以将其编码为((long long)x 32) | (y 0xffffffff)或者更简单地使用std::pairint, int作为键。但pair作为unordered_set的键需要自定义哈希函数稍显麻烦。在竞赛中为了追求速度我们更倾向于使用二维数组这就必须进行坐标平移。坐标平移策略找到所有初始点的最小横坐标min_x和最小纵坐标min_y。设定最大扩散时间T。确定我们需要搜索的网格范围横坐标从min_x - T到max_x T纵坐标从min_y - T到max_y T。其中max_x和max_y是初始点的最大坐标。定义平移量offset_x -(min_x - T)offset_y -(min_y - T)。这样平移后的新坐标nx x offset_xny y offset_y就都变成了非负数可以作为数组下标。例如min_x -1, T5那么最小需要覆盖的x是-1-5-6。令offset_x 6则x-6映射为0x-1映射为5x0映射为6以此类推。我们需要声明一个二维数组visited或dist。dist可以同时记录距离和访问状态-1表示未访问。int width (max_x T) - (min_x - T) 1; int height (max_y T) - (min_y - T) 1; vectorvectorint dist(height, vectorint(width, -1)); // 初始化为-1表示未访问这里width和height可能很大如果T很大使用vector动态分配更安全。如果经过估算后大小可控比如几百万个点也可以用静态数组。3.2 BFS队列的操作与层数记录BFS需要一个队列我们使用std::queue。队列的元素需要包含点的坐标信息。我们可以用一个结构体或者直接用pairint, int。层数记录技巧 BFS计算扩散到每个点的时间。在将初始点入队时将其距离设为0。当从队列中取出一个点(x, y)时设其距离为d。我们检查其四个邻居(nx, ny)。如果dist[ny][nx]为-1未访问则设置dist[ny][nx] d 1并将其坐标入队。这样每个点第一次被访问时记录的距离就是它被扩散到的最早时间。如果题目只要求计算T时刻的黑点数量那么当从队列中取出的点的距离d已经等于T时实际上这一层之后的点时间都会大于T对答案没有贡献。我们可以选择不再将新的点入队但已经入队的本层点仍需处理完。更简单的方法是让BFS正常进行最后遍历dist数组统计所有值不为-1且T的格子数量。一个关键的优化如果初始点很多且T很大最终黑点数量会非常多遍历整个dist数组可能很慢。我们可以在BFS过程中直接计数。初始化答案ans为初始点个数。每当成功访问一个新邻居即dist[ny][nx] d1时如果d1 T则ans。这样BFS结束答案也就出来了。3.3 边界判断与无限平面的处理在我们平移后的数组dist中下标范围是[0, height-1]和[0, width-1]。在BFS中每次生成邻居坐标(nx, ny)后必须检查其是否在我们定义的数组范围内。if(nx 0 nx width ny 0 ny height dist[ny][nx] -1) { // 执行访问和入队操作 }这个判断至关重要它确保了搜索不会越界同时也隐含了我们对“无限平面”的假设我们只关心在时间T内从初始点出发曼哈顿距离不超过T的这个菱形区域所覆盖的矩形范围。这个范围之外的区域在T时刻不可能被扩散到因此无需考虑。这就是将无限问题有界化的核心逻辑。3.4 完整代码框架与注释下面给出一个解决“计算T时刻黑点数量”问题的通用C代码框架。假设输入格式为第一行是初始点个数n和时间T接下来n行是每个初始点的坐标(x, y)。#include iostream #include vector #include queue #include algorithm #include climits using namespace std; // 方向数组上、下、左、右 const int dx[4] {0, 0, -1, 1}; const int dy[4] {-1, 1, 0, 0}; int main() { int n, T; cin n T; vectorpairint, int points(n); int min_x INT_MAX, max_x INT_MIN; int min_y INT_MAX, max_y INT_MIN; // 读入初始点并计算坐标范围 for(int i 0; i n; i) { cin points[i].first points[i].second; min_x min(min_x, points[i].first); max_x max(max_x, points[i].first); min_y min(min_y, points[i].second); max_y max(max_y, points[i].second); } // 计算搜索的矩形边界和平移量 int left min_x - T; int right max_x T; int bottom min_y - T; // 注意这里bottom对应min_y是y的最小值 int top max_y T; // top对应y的最大值 int width right - left 1; int height top - bottom 1; int offset_x -left; // 将left映射到0 int offset_y -bottom; // 将bottom映射到0 // 初始化距离数组 vectorvectorint dist(height, vectorint(width, -1)); queuepairint, int q; // 将初始点入队 for(auto p : points) { int nx p.first offset_x; int ny p.second offset_y; dist[ny][nx] 0; // 时间为0 q.push({nx, ny}); } long long ans n; // 起始时就有n个黑点 // 开始BFS while(!q.empty()) { auto [x, y] q.front(); q.pop(); int current_dist dist[y][x]; // 如果当前点的时间已经等于T其邻居时间将是T1超过限制无需继续从此点扩散 // 注意不能直接break因为队列里可能还有时间等于current_dist的点。 // 更准确地说如果current_dist T那么从这个点扩展出去的邻居时间肯定T对答案无贡献所以可以跳过扩展。 if(current_dist T) { continue; } for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查边界和是否访问过 if(nx 0 nx width ny 0 ny height dist[ny][nx] -1) { dist[ny][nx] current_dist 1; // 如果新点的时间没有超过T则计入答案 if(current_dist 1 T) { ans; } q.push({nx, ny}); } } } cout ans endl; return 0; }实操心得在竞赛中ans使用long long是很好的习惯因为当T很大时黑点数量可能超出int范围。坐标平移的计算要仔细检查加减号一个快速的验证方法是取一个初始点(x,y)计算其平移后的坐标(xoffset_x, yoffset_y)看是否在数组范围内且dist值被正确设为0。4. 性能优化与边界情况探讨上述框架是标准解法但对于极端数据比如T非常大达到10^9级别我们定义的二维数组将大到无法存储。这时就必须换用其他方法例如使用unordered_set只存储黑点或者寻找数学规律。但蓝桥杯国赛题通常会将T控制在一个使得BFS可解的范围内比如几千以内重点考察的是BFS的实现和优化细节。即便如此我们仍需关注一些优化点和边界情况。4.1 使用unordered_set的稀疏存储方案如果初始点非常稀疏而T又比较大导致width和height巨大但实际黑点数量答案可能远小于网格总数。这时用二维数组会浪费大量空间。我们可以用unordered_set来存储所有黑点的坐标编码后。编码方法为了将二维坐标(x, y)作为unordered_set的键我们需要一个哈希函数。一个简单可靠的方法是struct PairHash { size_t operator()(const pairint, int p) const { // 假设坐标在[-1e5, 1e5]之间可以映射到[0, 2e5] // 使用一个大于坐标范围的大质数进行混合 return (static_castsize_t(p.first 100000) 20) ^ static_castsize_t(p.second 100000); } }; unordered_setpairint, int, PairHash black_set;或者更简单地将坐标转换为字符串auto encode [](int x, int y) - string { return to_string(x) , to_string(y); }; unordered_setstring black_set;字符串编码简单但效率略低。在BFS时我们不再需要dist数组记录距离而是需要两个集合current当前时刻的黑点和next下一时刻将新增的黑点。我们还需要记录当前时间t。每一秒遍历current中的所有点生成它们的四个邻居。如果邻居不在black_set中即从未被染黑过则将其加入black_set和next。然后current nextnext清空t直到t T。最后black_set的大小就是答案。这种方法节省了空间但每次判断“是否访问过”需要哈希查找时间开销比数组的O(1)访问要大。它适用于“稀疏扩散”的场景。4.2 多源BFS的初始化与去重当多个初始点重合或彼此非常接近时在数组方案的BFS初始化中直接设置dist为0并入队即可队列会自然处理重复。在集合方案中初始化时需要将所有初始点加入black_set和初始的current集合。集合本身具有去重功能所以即使有重复坐标也没关系。一个易错点在数组BFS中如果多个初始点在同一起始时间入队BFS过程会正确合并它们的扩散波阵面。不需要特殊处理。4.3 时间复杂度的估算与控制设最终黑点数量为M。对于数组BFS我们至多访问M个点每个点尝试扩展4个方向总操作次数约为4M。加上初始化数组O(width*height)如果width*height远大于M则初始化是主要开销。对于集合BFS操作次数也是O(M)但每次哈希查找/插入有常数开销。如果题目中T非常大导致M也极大例如接近width*height那么两种方法的时间复杂度都可以接受但数组法的常数更小。如果T很大但初始点很少导致M远小于网格总数则集合法在空间上占优。竞赛策略通常优先实现数组BFS因为它编码简单、运行快。只有在内存计算明显不足时例如width*height 1e7且内存限制严格才考虑集合BFS。4.4 当问题变种求覆盖指定区域的最短时间“扩散”问题另一个常见的变种是求所有初始点扩散出的黑点需要多少秒才能完全覆盖一个给定的矩形区域或所有点这时BFS过程需要持续进行直到目标条件满足。解法我们不再以时间T为限制进行BFS而是让BFS一直进行下去。我们需要额外维护一个计数器或一个判断条件。例如如果目标是覆盖一个矩形区域[X1, X2] x [Y1, Y2]内的所有整点我们可以在BFS过程中每访问到一个新点就检查它是否在该矩形内。如果该矩形内总共有K个点我们可以用一个变量covered记录已经被访问到的矩形内点的数量。当covered K时当前从队列中取出的点的dist值即当前时间就是覆盖整个矩形所需的最短时间。这里的关键是BFS是按时间顺序扩展的所以第一个满足“矩形被完全覆盖”的时刻就是最短时间。实现时需要在BFS的主循环中增加条件判断和提前退出。5. 从“扩散”到更广泛的BFS应用场景解完这道题我们掌握的不仅仅是一道题的答案而是一种强大的建模工具——多源广度优先搜索。这种“波阵面推进”的模型可以解决大量看似不同的问题。1. 地图探索与最短路径在网格游戏中多个单位同时从不同位置出发探索未知区域求最早相遇时间或覆盖全图的时间。这本质上就是多源BFS。2. 火灾模拟或病毒传播多个火源同时开始燃烧火势每步向四邻域蔓延求某个位置被点燃的时间或者所有可燃物被点燃的时间。这就是“扩散”问题的直接应用。3. 图像处理中的区域生长在二值图像中从多个种子像素开始将颜色相似的相邻像素合并进来。可以使用BFS或DFS但BFS能保证生长区域是均匀扩大的。4. 网络爬虫的层级抓取从一批初始URL源点开始抓取网页并提取其中的新链接放入队列继续抓取。这里BFS的“层”对应着链接的跳转深度。5. 社交网络中的信息传播假设一个人发布一条消息他的所有朋友下一秒都会看到朋友的朋友再下一秒看到求消息传遍整个网络的时间。这可以用图上的BFS来模拟虽然现实网络更复杂。掌握多源BFS的关键在于识别出问题的“每一步代价相同”和“需要最短时间/距离”这两个特征。一旦识别出来剩下的就是熟练的编码和对边界条件的仔细处理。回到蓝桥杯这道题它之所以经典就在于它用一个简单的场景清晰地传达了这种算法思想。在竞赛和实际编程中遇到“扩散”、“蔓延”、“传播”、“覆盖”这类关键词时BFS应该成为你条件反射般的首选思路之一。通过精确的坐标处理、严谨的边界判断和清晰的状态记录你就能将这种思路转化为高效的代码解决一系列复杂的问题。 
长河君 · 2026/8/28 12:17:58 · 阅读 1.2k 蓝桥杯扩散题解析：多源BFS算法核心与网格问题实战
1. 项目概述从“扩散”到“广度优先搜索”的思维跃迁“第十一届蓝桥杯CB组国赛试题B扩散”这个标题对于参加过蓝桥杯的选手来说瞬间就能勾起一系列回忆和思考。蓝桥杯作为国内覆盖面极广的大学生IT赛事其国赛题目往往代表着当届竞赛的最高难度和最新颖的思维考察点。这道“扩散”题正是这样一个典型。它初看可能让人联想到物理现象或数学模型但实际上它是一道经典的、披着“模拟”外衣的图论搜索问题核心考察的是选手对广度优先搜索BFS算法的深刻理解与灵活应用能力以及对坐标系处理和边界判断的编程基本功。这道题之所以令人印象深刻是因为它用一个非常生活化的概念——“扩散”包装了一个需要严谨算法逻辑才能高效解决的问题。题目通常会描述在一个无限的二维网格平面上有若干个初始点称为“黑点”在时刻0被“感染”。此后每一秒每个黑点会向上、下、左、右四个方向扩散一格将其相邻的网格也变为黑点。问题最终会问在某个特定的时刻T比如2020秒平面上有多少个网格点被染黑或者所有初始点形成的连通区域需要多少秒才能覆盖一个指定范围这种模型在计算机科学中无处不在例如网络传播模拟、图像处理中的区域生长、游戏中的地图探索战争迷雾等。解决它蛮力模拟在无限平面上是不可行的必须抓住“扩散”的波阵面是均匀推进的这一本质将其转化为从多个源点同时开始的BFS过程。BFS的“队列”天然地刻画了时间顺序队列中每一“层”的点就对应着某一秒新被扩散到的点。理解到这一步就从“模拟题”跨入了“算法题”的门槛。接下来我们将彻底拆解这道题不仅给出标准解法更会深入探讨其中的优化技巧、易错细节以及如何将这种思维迁移到其他相似场景中。2. 核心思路解析为什么BFS是唯一正解面对“扩散”问题新手最容易陷入的误区就是尝试直接模拟整个无限平面。他们会想开一个足够大的二维数组比如map[10000][10000]把初始点放进去然后循环T次每次遍历所有黑点并向四周扩散。这种方法在T很小、初始点很少时勉强可行但一旦T达到题目常见的上千量级无论时间还是空间复杂度都是灾难性的。时间复杂度是O(T * N * M)N、M为数组维度空间则是O(N*M)极易超时和内存超限。因此我们必须转换视角。关键洞察在于一个点被染黑的时刻等于它到任意一个初始点的最短曼哈顿距离。曼哈顿距离即两点在标准坐标系下横纵坐标差的绝对值之和。为什么因为扩散每次只能向四邻域移动一格所以从初始点“走”到目标点所需的最少步数时间就是曼哈顿距离。一个点可能被多个初始点扩散到它被染黑的时刻就是所有初始点中距离它最近的那个曼哈顿距离。于是问题转化为给定平面上若干个初始点对于平面上某个点或在某个范围内所有点求其到所有初始点的最小曼哈顿距离。如果问题是求T时刻有多少个点被覆盖那就是统计所有满足min_distance T的点数。那么如何高效计算呢这就是BFS登场的时候。BFS非常适合求解这种“从多个源点出发每一步代价相同”的最短路径问题。我们可以将所有初始点同时放入队列并标记其距离时间为0。然后进行标准的BFS每次从队列取出一个点检查其上下左右四个邻居。如果邻居未被访问过则其距离等于当前点距离1将其入队。这个过程会像水波一样一圈圈荡开当队列为空或者当我们扩展到足够的时间T时所有被访问到的点及其对应的“被感染时间”就都计算出来了。为什么不用深度优先搜索DFSDFS会一条路走到黑无法保证最先找到的解就是最短路径最小时间它求出的“距离”没有意义。而BFS按层推进的特性保证了第一次访问到某个节点时所用的步数一定是最少的。为什么不用直接计算曼哈顿距离对于“统计T时刻黑点数量”这类问题如果平面范围是无限的我们确实可以通过数学方法计算。例如一个初始点在第T秒后会形成一个中心在初始点、曼哈顿距离为T的菱形或称正方形旋转45度区域。多个初始点形成的区域会有重叠。计算多个菱形区域的并集面积涉及计算几何非常复杂且容易出错尤其是在需要处理整数格点的情况下。而BFS模拟扩散过程思路直观实现相对稳健是竞赛中的首选方法。注意BFS解法隐含了一个前提——平面在理论上是无限的但在计算机中我们必须设定一个搜索范围。这个范围需要根据初始点坐标和最大时间T来估算通常是[min_x - T, max_x T]和[min_y - T, max_y T]这个矩形区域。这是将无限问题有限化的关键一步也是容易出错的地方范围估小了会漏点估大了可能超时或超内存。3. 算法实现细节与关键步骤拆解理解了BFS是核心接下来我们深入到代码层面拆解每一个关键步骤。我将以C为例因为这是蓝桥杯CB组的比赛语言。我们会从数据结构选择、坐标处理、去重判断到完整代码框架一步步说明。3.1 数据结构设计与坐标映射在网格BFS中我们通常需要记录某个坐标点是否被访问过以及被访问时的时间距离。由于坐标可能是负数初始点可能在原点四周而C数组下标不能为负我们需要进行坐标映射。一种常见且安全的方法是使用std::unordered_set或std::set来存储已访问的点。我们可以将二维坐标编码成一个long long类型的整数。例如对于一个点(x, y)我们可以将其编码为((long long)x 32) | (y 0xffffffff)或者更简单地使用std::pairint, int作为键。但pair作为unordered_set的键需要自定义哈希函数稍显麻烦。在竞赛中为了追求速度我们更倾向于使用二维数组这就必须进行坐标平移。坐标平移策略找到所有初始点的最小横坐标min_x和最小纵坐标min_y。设定最大扩散时间T。确定我们需要搜索的网格范围横坐标从min_x - T到max_x T纵坐标从min_y - T到max_y T。其中max_x和max_y是初始点的最大坐标。定义平移量offset_x -(min_x - T)offset_y -(min_y - T)。这样平移后的新坐标nx x offset_xny y offset_y就都变成了非负数可以作为数组下标。例如min_x -1, T5那么最小需要覆盖的x是-1-5-6。令offset_x 6则x-6映射为0x-1映射为5x0映射为6以此类推。我们需要声明一个二维数组visited或dist。dist可以同时记录距离和访问状态-1表示未访问。int width (max_x T) - (min_x - T) 1; int height (max_y T) - (min_y - T) 1; vectorvectorint dist(height, vectorint(width, -1)); // 初始化为-1表示未访问这里width和height可能很大如果T很大使用vector动态分配更安全。如果经过估算后大小可控比如几百万个点也可以用静态数组。3.2 BFS队列的操作与层数记录BFS需要一个队列我们使用std::queue。队列的元素需要包含点的坐标信息。我们可以用一个结构体或者直接用pairint, int。层数记录技巧 BFS计算扩散到每个点的时间。在将初始点入队时将其距离设为0。当从队列中取出一个点(x, y)时设其距离为d。我们检查其四个邻居(nx, ny)。如果dist[ny][nx]为-1未访问则设置dist[ny][nx] d 1并将其坐标入队。这样每个点第一次被访问时记录的距离就是它被扩散到的最早时间。如果题目只要求计算T时刻的黑点数量那么当从队列中取出的点的距离d已经等于T时实际上这一层之后的点时间都会大于T对答案没有贡献。我们可以选择不再将新的点入队但已经入队的本层点仍需处理完。更简单的方法是让BFS正常进行最后遍历dist数组统计所有值不为-1且T的格子数量。一个关键的优化如果初始点很多且T很大最终黑点数量会非常多遍历整个dist数组可能很慢。我们可以在BFS过程中直接计数。初始化答案ans为初始点个数。每当成功访问一个新邻居即dist[ny][nx] d1时如果d1 T则ans。这样BFS结束答案也就出来了。3.3 边界判断与无限平面的处理在我们平移后的数组dist中下标范围是[0, height-1]和[0, width-1]。在BFS中每次生成邻居坐标(nx, ny)后必须检查其是否在我们定义的数组范围内。if(nx 0 nx width ny 0 ny height dist[ny][nx] -1) { // 执行访问和入队操作 }这个判断至关重要它确保了搜索不会越界同时也隐含了我们对“无限平面”的假设我们只关心在时间T内从初始点出发曼哈顿距离不超过T的这个菱形区域所覆盖的矩形范围。这个范围之外的区域在T时刻不可能被扩散到因此无需考虑。这就是将无限问题有界化的核心逻辑。3.4 完整代码框架与注释下面给出一个解决“计算T时刻黑点数量”问题的通用C代码框架。假设输入格式为第一行是初始点个数n和时间T接下来n行是每个初始点的坐标(x, y)。#include iostream #include vector #include queue #include algorithm #include climits using namespace std; // 方向数组上、下、左、右 const int dx[4] {0, 0, -1, 1}; const int dy[4] {-1, 1, 0, 0}; int main() { int n, T; cin n T; vectorpairint, int points(n); int min_x INT_MAX, max_x INT_MIN; int min_y INT_MAX, max_y INT_MIN; // 读入初始点并计算坐标范围 for(int i 0; i n; i) { cin points[i].first points[i].second; min_x min(min_x, points[i].first); max_x max(max_x, points[i].first); min_y min(min_y, points[i].second); max_y max(max_y, points[i].second); } // 计算搜索的矩形边界和平移量 int left min_x - T; int right max_x T; int bottom min_y - T; // 注意这里bottom对应min_y是y的最小值 int top max_y T; // top对应y的最大值 int width right - left 1; int height top - bottom 1; int offset_x -left; // 将left映射到0 int offset_y -bottom; // 将bottom映射到0 // 初始化距离数组 vectorvectorint dist(height, vectorint(width, -1)); queuepairint, int q; // 将初始点入队 for(auto p : points) { int nx p.first offset_x; int ny p.second offset_y; dist[ny][nx] 0; // 时间为0 q.push({nx, ny}); } long long ans n; // 起始时就有n个黑点 // 开始BFS while(!q.empty()) { auto [x, y] q.front(); q.pop(); int current_dist dist[y][x]; // 如果当前点的时间已经等于T其邻居时间将是T1超过限制无需继续从此点扩散 // 注意不能直接break因为队列里可能还有时间等于current_dist的点。 // 更准确地说如果current_dist T那么从这个点扩展出去的邻居时间肯定T对答案无贡献所以可以跳过扩展。 if(current_dist T) { continue; } for(int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查边界和是否访问过 if(nx 0 nx width ny 0 ny height dist[ny][nx] -1) { dist[ny][nx] current_dist 1; // 如果新点的时间没有超过T则计入答案 if(current_dist 1 T) { ans; } q.push({nx, ny}); } } } cout ans endl; return 0; }实操心得在竞赛中ans使用long long是很好的习惯因为当T很大时黑点数量可能超出int范围。坐标平移的计算要仔细检查加减号一个快速的验证方法是取一个初始点(x,y)计算其平移后的坐标(xoffset_x, yoffset_y)看是否在数组范围内且dist值被正确设为0。4. 性能优化与边界情况探讨上述框架是标准解法但对于极端数据比如T非常大达到10^9级别我们定义的二维数组将大到无法存储。这时就必须换用其他方法例如使用unordered_set只存储黑点或者寻找数学规律。但蓝桥杯国赛题通常会将T控制在一个使得BFS可解的范围内比如几千以内重点考察的是BFS的实现和优化细节。即便如此我们仍需关注一些优化点和边界情况。4.1 使用unordered_set的稀疏存储方案如果初始点非常稀疏而T又比较大导致width和height巨大但实际黑点数量答案可能远小于网格总数。这时用二维数组会浪费大量空间。我们可以用unordered_set来存储所有黑点的坐标编码后。编码方法为了将二维坐标(x, y)作为unordered_set的键我们需要一个哈希函数。一个简单可靠的方法是struct PairHash { size_t operator()(const pairint, int p) const { // 假设坐标在[-1e5, 1e5]之间可以映射到[0, 2e5] // 使用一个大于坐标范围的大质数进行混合 return (static_castsize_t(p.first 100000) 20) ^ static_castsize_t(p.second 100000); } }; unordered_setpairint, int, PairHash black_set;或者更简单地将坐标转换为字符串auto encode [](int x, int y) - string { return to_string(x) , to_string(y); }; unordered_setstring black_set;字符串编码简单但效率略低。在BFS时我们不再需要dist数组记录距离而是需要两个集合current当前时刻的黑点和next下一时刻将新增的黑点。我们还需要记录当前时间t。每一秒遍历current中的所有点生成它们的四个邻居。如果邻居不在black_set中即从未被染黑过则将其加入black_set和next。然后current nextnext清空t直到t T。最后black_set的大小就是答案。这种方法节省了空间但每次判断“是否访问过”需要哈希查找时间开销比数组的O(1)访问要大。它适用于“稀疏扩散”的场景。4.2 多源BFS的初始化与去重当多个初始点重合或彼此非常接近时在数组方案的BFS初始化中直接设置dist为0并入队即可队列会自然处理重复。在集合方案中初始化时需要将所有初始点加入black_set和初始的current集合。集合本身具有去重功能所以即使有重复坐标也没关系。一个易错点在数组BFS中如果多个初始点在同一起始时间入队BFS过程会正确合并它们的扩散波阵面。不需要特殊处理。4.3 时间复杂度的估算与控制设最终黑点数量为M。对于数组BFS我们至多访问M个点每个点尝试扩展4个方向总操作次数约为4M。加上初始化数组O(width*height)如果width*height远大于M则初始化是主要开销。对于集合BFS操作次数也是O(M)但每次哈希查找/插入有常数开销。如果题目中T非常大导致M也极大例如接近width*height那么两种方法的时间复杂度都可以接受但数组法的常数更小。如果T很大但初始点很少导致M远小于网格总数则集合法在空间上占优。竞赛策略通常优先实现数组BFS因为它编码简单、运行快。只有在内存计算明显不足时例如width*height 1e7且内存限制严格才考虑集合BFS。4.4 当问题变种求覆盖指定区域的最短时间“扩散”问题另一个常见的变种是求所有初始点扩散出的黑点需要多少秒才能完全覆盖一个给定的矩形区域或所有点这时BFS过程需要持续进行直到目标条件满足。解法我们不再以时间T为限制进行BFS而是让BFS一直进行下去。我们需要额外维护一个计数器或一个判断条件。例如如果目标是覆盖一个矩形区域[X1, X2] x [Y1, Y2]内的所有整点我们可以在BFS过程中每访问到一个新点就检查它是否在该矩形内。如果该矩形内总共有K个点我们可以用一个变量covered记录已经被访问到的矩形内点的数量。当covered K时当前从队列中取出的点的dist值即当前时间就是覆盖整个矩形所需的最短时间。这里的关键是BFS是按时间顺序扩展的所以第一个满足“矩形被完全覆盖”的时刻就是最短时间。实现时需要在BFS的主循环中增加条件判断和提前退出。5. 从“扩散”到更广泛的BFS应用场景解完这道题我们掌握的不仅仅是一道题的答案而是一种强大的建模工具——多源广度优先搜索。这种“波阵面推进”的模型可以解决大量看似不同的问题。1. 地图探索与最短路径在网格游戏中多个单位同时从不同位置出发探索未知区域求最早相遇时间或覆盖全图的时间。这本质上就是多源BFS。2. 火灾模拟或病毒传播多个火源同时开始燃烧火势每步向四邻域蔓延求某个位置被点燃的时间或者所有可燃物被点燃的时间。这就是“扩散”问题的直接应用。3. 图像处理中的区域生长在二值图像中从多个种子像素开始将颜色相似的相邻像素合并进来。可以使用BFS或DFS但BFS能保证生长区域是均匀扩大的。4. 网络爬虫的层级抓取从一批初始URL源点开始抓取网页并提取其中的新链接放入队列继续抓取。这里BFS的“层”对应着链接的跳转深度。5. 社交网络中的信息传播假设一个人发布一条消息他的所有朋友下一秒都会看到朋友的朋友再下一秒看到求消息传遍整个网络的时间。这可以用图上的BFS来模拟虽然现实网络更复杂。掌握多源BFS的关键在于识别出问题的“每一步代价相同”和“需要最短时间/距离”这两个特征。一旦识别出来剩下的就是熟练的编码和对边界条件的仔细处理。回到蓝桥杯这道题它之所以经典就在于它用一个简单的场景清晰地传达了这种算法思想。在竞赛和实际编程中遇到“扩散”、“蔓延”、“传播”、“覆盖”这类关键词时BFS应该成为你条件反射般的首选思路之一。通过精确的坐标处理、严谨的边界判断和清晰的状态记录你就能将这种思路转化为高效的代码解决一系列复杂的问题。