1. 从“扩散”到“BFS”一道国赛题的解题脉络看到“扩散”这个标题很多参加过蓝桥杯的同学可能会心一笑。这几乎是蓝桥杯国赛级别题目里一个非常经典的“套路”题目描述听起来可能像物理现象或者数学模型但最终的解题钥匙往往就藏在“广度优先搜索”这个算法里。我参加过多次蓝桥杯的辅导和评审工作发现很多同学在考场上面对这类题目时最大的障碍不是不会BFS而是无法从“扩散”这个生活化的描述中精准地抽象出BFS的模型。这道来自第十一届蓝桥杯国赛的题目就是一个绝佳的例子它考察的远不止是BFS的模板背诵更是对问题建模和算法应用边界理解的深度。简单来说这道题描述了一个在无限大网格上的“扩散”过程初始时刻在网格的某些特定坐标点上有一个“黑点”。此后每一秒黑点会向其上下左右四个相邻的网格点扩散。题目最终会问在第T秒时有多少个网格点被染黑。如果你直接去模拟这个物理过程在无限大的网格上这几乎是一个不可能完成的任务。但如果你立刻意识到一个点从初始位置扩散到另一个点所需的时间恰好等于这两个点之间的曼哈顿距离那么整个问题就豁然开朗了。BFS在这里的角色就是帮助我们系统性地、高效地计算出所有在时间T内能被“波及”到的点。所以这篇文章我不会仅仅带大家走一遍BFS的代码。我想深入聊聊当你拿到一个以“扩散”为名的题目时应该如何一步步拆解确认它是否能用BFS解决以及如何设计BFS中的每一个关键环节——队列、状态、判重和终止条件。我们会以这道国赛题为蓝本把思路彻底理清让你以后再遇到“感染”、“传播”、“覆盖”这类关键词时能条件反射般地构建出正确的搜索模型。2. 问题本质剖析曼哈顿距离与BFS的等价关系我们首先必须跳出“模拟扩散”这个直观但低效的思维陷阱。题目中描述的是每秒向四邻域扩散这是一个离散化的过程。假设有一个初始黑点位于(x0, y0)。那么第0秒只有(x0, y0)是黑的。第1秒(x0, y0)以及(x0±1, y0),(x0, y0±1)变成黑的。第2秒上述黑点继续向外扩散……关键在于一个点(x, y)从初始点(x0, y0)被染黑所需的最短时间是多少思考一下扩散的路径从(x0, y0)走到(x, y)每次只能走上下左右一步。那么所需的最少步数正是这两个点之间的曼哈顿距离计算公式为|x - x0| |y - y0|。注意这里有一个非常重要的前提即扩散是同时从所有初始点开始、并且互不干扰地进行的。也就是说一个点可能被多个初始点扩散到但它被染黑的时刻是所有初始点扩散到它的时间中的最小值。因为只要有一个源点能在时间T内到达它它就在T时刻变黑了。因此整个“扩散”问题被转化为了一个计算几何问题给定平面上N个初始点源点对于无限网格中的任意点(x, y)我们计算它到所有源点的曼哈顿距离并取最小值记为minDist(x, y)。那么在时刻T被染黑的点就是所有满足minDist(x, y) T的点(x, y)的集合。那么BFS在这里有什么用BFS恰恰是计算这种“最小步数”即曼哈顿距离的天然工具。我们可以把每个网格点看作图中的一个节点相邻的上下左右点之间有边相连。从所有源点同时开始进行BFS第一次访问到某个节点所经历的“层数”也就是步数就是该点的minDist。BFS的队列机制保证了我们总是按距离从近到远的顺序访问节点这完美契合了“扩散”的过程。所以解题的核心思路就清晰了建模将网格视为图格点为节点四邻域连通为边。多源BFS将所有初始黑点作为BFS的起点同时放入队列并标记其距离为0。搜索不断从队列中取出点向其四个方向扩展。如果扩展到的点未被访问过则其距离为当前点距离1并将其加入队列。统计当BFS过程进行到“距离”大于T时就可以停止。所有“距离”值小于等于T的点就是T时刻的黑点总数。这里最大的优化点在于我们无需真的去遍历一个无限大的网格。因为扩散范围受时间T限制黑点最多扩散到以各个源点为中心、曼哈顿距离为T的菱形区域想象一个旋转了45度的正方形。所有需要被考虑的点都在这些区域的并集内。在BFS中这个限制自然由搜索的层数距离来控制我们只探索距离不超过T的点。3. 多源BFS的实现细节与关键陷阱理解了原理我们来动手实现。这里有几个实现上的细节和容易踩坑的地方我结合自己的经验详细说明。3.1 数据结构的选择与坐标处理首先面临的是无限网格的表示问题。我们显然不能在内存中开辟一个无限的二维数组。最常用的方法是使用哈希表在Python中是dict在C中是unordered_map来存储那些被访问过的点的状态。键可以是点的坐标值可以是该点被染黑的时间距离。对于坐标一个常见的技巧是进行偏移。因为题目给出的坐标可能为负数而数组索引通常从0开始。我们可以选择一个足够大的基数例如OFFSET 3000因为时间T可能很大扩散范围也大将所有坐标加上这个偏移量映射到非负区间这样就可以用二维数组来存储了。但使用哈希表则更为灵活无需担心偏移量是否足够大。队列使用标准的队列数据结构。在Python中可以用collections.deque在C中用queuepairint, int。访问与距离记录我们需要一个快速的数据结构来记录某个点是否已被访问以及是在何时距离被访问的。使用字典哈希表是最佳选择visited {}键为(x, y)元组值为距离。3.2 多源BFS的初始化这是区别于单源BFS的关键一步。单源BFS只有一个起点多源则有多个。初始化时我们需要将所有初始点同时加入队列并标记它们的距离为0。from collections import deque # 假设初始点列表为 sources [(x1, y1), (x2, y2), ...] queue deque() visited {} # 使用字典记录点和距离 for x, y in sources: visited[(x, y)] 0 # 距离为0 queue.append((x, y, 0)) # 队列中存储 (x, y, distance)注意我在这里把距离也存入了队列。另一种等价的写法是在从队列中取出节点时通过visited字典来查询当前节点的距离。两种方式都可以但将距离存入队列有时写起来更清晰。3.3 搜索边界的控制与终止条件BFS需要向四个方向上(0,1)下(0,-1)左(-1,0)右(1,0)进行扩展。对于每个扩展出的新点(nx, ny)我们进行如下判断如果(nx, ny)已经在visited字典中说明它已经被更早地访问到了距离更小跳过。否则计算其距离new_dist current_dist 1。如果new_dist T说明这个点是在T时刻之后才被扩散到的我们不仅不能把它加入队列甚至可以停止向这个方向继续深入搜索吗这里有个陷阱不能因为new_dist T就完全停止。因为BFS是按层遍历的当从队列中取出的一个点的current_dist已经等于T时从这个点扩展出去的所有点的new_dist都将是T1已经超出了时间限制。所以更优雅的终止条件是在从队列中取出节点时判断如果取出的节点距离等于T那么从这个节点扩展出去的点距离就是T1无需继续扩展该节点但队列中可能还有距离小于T的其他节点需要处理。或者我们可以在扩展前判断new_dist T只有满足条件的点才加入队列和visited字典。一个高效的写法while queue: x, y, dist queue.popleft() # 如果当前点的距离已经等于T则从它扩展出去的点必然超过T无需再扩展此点。 # 但注意队列中可能还存在dist T的点它们仍需被处理。 if dist T: continue # 跳过此点的扩展继续处理队列中其他点 for dx, dy in directions: nx, ny x dx, y dy if (nx, ny) not in visited: new_dist dist 1 # 只有距离在T范围内的点才需要被记录和继续探索 if new_dist T: visited[(nx, ny)] new_dist queue.append((nx, ny, new_dist))这个写法确保了visited字典里只记录距离在[0, T]之间的点并且队列中不会出现距离大于T的点。3.4 统计结果与复杂度分析当BFS队列为空时visited字典中存储的就是所有在T时刻及之前被染黑的点。字典的大小就是黑点的总数。时间复杂度最坏情况下我们需要访问所有距离源点曼哈顿距离不超过T的点。这些点构成一个复杂的多边形区域。点的数量级大约是O((T * sqrt(N))^2)级别对于BFS来说是可以接受的。使用哈希表使得每次查找和插入的平均时间复杂度为O(1)。空间复杂度主要消耗在visited字典和队列上与需要访问的点数成线性关系。4. 从解题到举一反三BFS解决扩散类问题的模式通过这道国赛题我们可以总结出一套用BFS解决“扩散”、“感染”、“覆盖”类问题的通用方法论。当你下次遇到类似问题时可以按以下步骤思考第一步问题转化与建模确认移动规则通常是上下左右四连通或包括对角线八连通的网格移动。本题是四连通。确认“距离”定义在网格中步数通常等价于曼哈顿距离四连通或切比雪夫距离八连通。本题是曼哈顿距离。判断是否多源初始状态是否有多个起点本题是。理解状态每个网格点就是一个状态。状态是否只取决于位置还是有其他属性如时间、方向等本题状态就是(x, y)坐标。第二步设计BFS核心要素状态表示用什么数据结构表示一个状态本题用(x, y)元组。队列初始化将所有初始状态加入队列并标记其“距离”或“层数”为0。状态扩展根据规则从当前状态可以衍生出哪些新状态本题是向四个方向走一步。判重与剪枝如何判断一个状态是否已被访问过本题用visited字典。哪些状态是无须探索的本题是距离超过T的状态。终止条件BFS何时结束本题有两个条件1) 队列为空自然结束2) 当前处理的状态距离已达到T可以提前停止该分支的扩展但队列可能不空。第三步实现与优化选择合适的数据结构队列、哈希表。注意坐标边界处理本题无限大无需处理越界但某些题有限制。在搜索过程中直接计算或收集答案。第四步测试与验证对于这类题目可以用小数据验证。例如只有一个源点(0,0)T1。那么黑点应该是(0,0),(1,0),(-1,0),(0,1),(0,-1)共5个。手动计算和程序跑出的结果应该一致。5. 常见变体与思路延伸掌握了基础模型我们来看看可能出现的变体这能帮助你在赛场上更灵活地应对。变体一带有阻碍物的扩散如果网格中某些点是障碍物无法被扩散也无法穿过。这需要在BFS扩展时增加一个判断如果扩展到的点是障碍物则不能从该点通过。visited字典也需要记录障碍物状态。这实际上变成了在网格地图上的标准BFS。变体二扩散速度不同如果不是每秒扩散一格而是某些方向或某些区域的扩散速度不同。这可以通过给边赋予不同的“权值”或“代价”来建模。这时BFS就不适用了因为BFS只适用于边权为1的图。需要改用Dijkstra算法如果权值为正来求单源最短路径或者多源Dijkstra。变体三求恰好第T秒新变黑的点本题是求第T秒时所有黑点。如果问题是“第T秒这一秒内新变黑了多少点”那么答案就是visited字典中距离值恰好等于T的点的数量。只需要在BFS过程中或结束后统计dist T的点即可。变体四三维空间扩散原理完全一样只是状态从(x, y)变成了(x, y, z)扩展方向从4个上下左右变成了6个上下左右前后。BFS的代码结构几乎不变只需修改状态表示和方向数组。6. 实战代码与逐行解析下面给出一个Python的参考实现并加上详细注释。我们假设初始点已经给定时间T也已给定。from collections import deque def bfs_diffusion(initial_points, T): 计算在时刻T被扩散覆盖的网格点数量。 :param initial_points: 初始黑点列表例如 [(0,0), (2020,11), (11,14), (2000,2000)] :param T: 时间限制 :return: 被覆盖的点的数量 # 方向数组上下左右 directions [(0, 1), (0, -1), (-1, 0), (1, 0)] # visited字典键为坐标元组(x, y)值为该点被访问时的距离时间 visited {} # 队列元素为 (x, y, distance) queue deque() # 多源BFS初始化所有初始点距离为0入队 for x, y in initial_points: visited[(x, y)] 0 queue.append((x, y, 0)) # 开始BFS while queue: x, y, dist queue.popleft() # 关键优化如果当前点距离已经等于T则从它扩展出的点距离为T1超出限制无需再扩展此点。 # 但队列中其他距离小于T的点仍需处理。 if dist T: continue # 向四个方向扩展 for dx, dy in directions: nx, ny x dx, y dy new_dist dist 1 # 如果新点未被访问过且新距离在T范围内 if (nx, ny) not in visited and new_dist T: visited[(nx, ny)] new_dist queue.append((nx, ny, new_dist)) # visited字典中存储了所有距离在[0, T]之间的点其长度即为答案 return len(visited) # 假设这是题目中的初始点 initial_points [(0, 0), (2020, 11), (11, 14), (2000, 2000)] T 2020 # 假设T2020 result bfs_diffusion(initial_points, T) print(f在时刻 {T}被覆盖的点数为{result})逐行解析与技巧visited使用字典而不是集合是因为我们不仅需要记录点是否被访问还需要记录它是在何时距离被访问的。虽然在本函数最终只用了它的键点坐标但在调试或处理变体问题时记录距离信息很有用。队列中存储了(x, y, dist)。这里dist是冗余的因为可以通过visited[(x, y)]获取。但存储它可以避免每次扩展时都去字典里查询一次对于性能密集型场景如C可能稍有帮助在Python中区别不大但代码更清晰。if dist T: continue这一行是重要的剪枝。它防止了程序去探索那些“即使能到达也已经在时间限制之外”的点减少了不必要的队列操作和字典查询。判断(nx, ny) not in visited和new_dist T的顺序先判断是否访问过再计算新距离和判断范围在逻辑上没问题。但有些写法会先计算新坐标然后判断新距离是否T再判断是否访问过。两种都可以但当前写法更符合“只有可能合格的候选点才去检查是否重复”的直觉。最终答案就是len(visited)。因为visited包含了所有初始点和在扩散过程中被访问到的、距离不超过T的点。这道“扩散”题本质上是一道多源BFS的模板题但其价值在于清晰地揭示了如何将现实世界的“扩散”过程抽象为图论中的最短路径问题。国赛出这样的题意在检验选手的基础算法应用能力和建模思维。记住这个模式下次无论是蓝桥杯还是其他算法竞赛再遇到“扩散”你就能稳稳地拿下。 蓝桥杯国赛经典题型解析：从“扩散”问题到多源BFS算法实现
1. 从“扩散”到“BFS”一道国赛题的解题脉络看到“扩散”这个标题很多参加过蓝桥杯的同学可能会心一笑。这几乎是蓝桥杯国赛级别题目里一个非常经典的“套路”题目描述听起来可能像物理现象或者数学模型但最终的解题钥匙往往就藏在“广度优先搜索”这个算法里。我参加过多次蓝桥杯的辅导和评审工作发现很多同学在考场上面对这类题目时最大的障碍不是不会BFS而是无法从“扩散”这个生活化的描述中精准地抽象出BFS的模型。这道来自第十一届蓝桥杯国赛的题目就是一个绝佳的例子它考察的远不止是BFS的模板背诵更是对问题建模和算法应用边界理解的深度。简单来说这道题描述了一个在无限大网格上的“扩散”过程初始时刻在网格的某些特定坐标点上有一个“黑点”。此后每一秒黑点会向其上下左右四个相邻的网格点扩散。题目最终会问在第T秒时有多少个网格点被染黑。如果你直接去模拟这个物理过程在无限大的网格上这几乎是一个不可能完成的任务。但如果你立刻意识到一个点从初始位置扩散到另一个点所需的时间恰好等于这两个点之间的曼哈顿距离那么整个问题就豁然开朗了。BFS在这里的角色就是帮助我们系统性地、高效地计算出所有在时间T内能被“波及”到的点。所以这篇文章我不会仅仅带大家走一遍BFS的代码。我想深入聊聊当你拿到一个以“扩散”为名的题目时应该如何一步步拆解确认它是否能用BFS解决以及如何设计BFS中的每一个关键环节——队列、状态、判重和终止条件。我们会以这道国赛题为蓝本把思路彻底理清让你以后再遇到“感染”、“传播”、“覆盖”这类关键词时能条件反射般地构建出正确的搜索模型。2. 问题本质剖析曼哈顿距离与BFS的等价关系我们首先必须跳出“模拟扩散”这个直观但低效的思维陷阱。题目中描述的是每秒向四邻域扩散这是一个离散化的过程。假设有一个初始黑点位于(x0, y0)。那么第0秒只有(x0, y0)是黑的。第1秒(x0, y0)以及(x0±1, y0),(x0, y0±1)变成黑的。第2秒上述黑点继续向外扩散……关键在于一个点(x, y)从初始点(x0, y0)被染黑所需的最短时间是多少思考一下扩散的路径从(x0, y0)走到(x, y)每次只能走上下左右一步。那么所需的最少步数正是这两个点之间的曼哈顿距离计算公式为|x - x0| |y - y0|。注意这里有一个非常重要的前提即扩散是同时从所有初始点开始、并且互不干扰地进行的。也就是说一个点可能被多个初始点扩散到但它被染黑的时刻是所有初始点扩散到它的时间中的最小值。因为只要有一个源点能在时间T内到达它它就在T时刻变黑了。因此整个“扩散”问题被转化为了一个计算几何问题给定平面上N个初始点源点对于无限网格中的任意点(x, y)我们计算它到所有源点的曼哈顿距离并取最小值记为minDist(x, y)。那么在时刻T被染黑的点就是所有满足minDist(x, y) T的点(x, y)的集合。那么BFS在这里有什么用BFS恰恰是计算这种“最小步数”即曼哈顿距离的天然工具。我们可以把每个网格点看作图中的一个节点相邻的上下左右点之间有边相连。从所有源点同时开始进行BFS第一次访问到某个节点所经历的“层数”也就是步数就是该点的minDist。BFS的队列机制保证了我们总是按距离从近到远的顺序访问节点这完美契合了“扩散”的过程。所以解题的核心思路就清晰了建模将网格视为图格点为节点四邻域连通为边。多源BFS将所有初始黑点作为BFS的起点同时放入队列并标记其距离为0。搜索不断从队列中取出点向其四个方向扩展。如果扩展到的点未被访问过则其距离为当前点距离1并将其加入队列。统计当BFS过程进行到“距离”大于T时就可以停止。所有“距离”值小于等于T的点就是T时刻的黑点总数。这里最大的优化点在于我们无需真的去遍历一个无限大的网格。因为扩散范围受时间T限制黑点最多扩散到以各个源点为中心、曼哈顿距离为T的菱形区域想象一个旋转了45度的正方形。所有需要被考虑的点都在这些区域的并集内。在BFS中这个限制自然由搜索的层数距离来控制我们只探索距离不超过T的点。3. 多源BFS的实现细节与关键陷阱理解了原理我们来动手实现。这里有几个实现上的细节和容易踩坑的地方我结合自己的经验详细说明。3.1 数据结构的选择与坐标处理首先面临的是无限网格的表示问题。我们显然不能在内存中开辟一个无限的二维数组。最常用的方法是使用哈希表在Python中是dict在C中是unordered_map来存储那些被访问过的点的状态。键可以是点的坐标值可以是该点被染黑的时间距离。对于坐标一个常见的技巧是进行偏移。因为题目给出的坐标可能为负数而数组索引通常从0开始。我们可以选择一个足够大的基数例如OFFSET 3000因为时间T可能很大扩散范围也大将所有坐标加上这个偏移量映射到非负区间这样就可以用二维数组来存储了。但使用哈希表则更为灵活无需担心偏移量是否足够大。队列使用标准的队列数据结构。在Python中可以用collections.deque在C中用queuepairint, int。访问与距离记录我们需要一个快速的数据结构来记录某个点是否已被访问以及是在何时距离被访问的。使用字典哈希表是最佳选择visited {}键为(x, y)元组值为距离。3.2 多源BFS的初始化这是区别于单源BFS的关键一步。单源BFS只有一个起点多源则有多个。初始化时我们需要将所有初始点同时加入队列并标记它们的距离为0。from collections import deque # 假设初始点列表为 sources [(x1, y1), (x2, y2), ...] queue deque() visited {} # 使用字典记录点和距离 for x, y in sources: visited[(x, y)] 0 # 距离为0 queue.append((x, y, 0)) # 队列中存储 (x, y, distance)注意我在这里把距离也存入了队列。另一种等价的写法是在从队列中取出节点时通过visited字典来查询当前节点的距离。两种方式都可以但将距离存入队列有时写起来更清晰。3.3 搜索边界的控制与终止条件BFS需要向四个方向上(0,1)下(0,-1)左(-1,0)右(1,0)进行扩展。对于每个扩展出的新点(nx, ny)我们进行如下判断如果(nx, ny)已经在visited字典中说明它已经被更早地访问到了距离更小跳过。否则计算其距离new_dist current_dist 1。如果new_dist T说明这个点是在T时刻之后才被扩散到的我们不仅不能把它加入队列甚至可以停止向这个方向继续深入搜索吗这里有个陷阱不能因为new_dist T就完全停止。因为BFS是按层遍历的当从队列中取出的一个点的current_dist已经等于T时从这个点扩展出去的所有点的new_dist都将是T1已经超出了时间限制。所以更优雅的终止条件是在从队列中取出节点时判断如果取出的节点距离等于T那么从这个节点扩展出去的点距离就是T1无需继续扩展该节点但队列中可能还有距离小于T的其他节点需要处理。或者我们可以在扩展前判断new_dist T只有满足条件的点才加入队列和visited字典。一个高效的写法while queue: x, y, dist queue.popleft() # 如果当前点的距离已经等于T则从它扩展出去的点必然超过T无需再扩展此点。 # 但注意队列中可能还存在dist T的点它们仍需被处理。 if dist T: continue # 跳过此点的扩展继续处理队列中其他点 for dx, dy in directions: nx, ny x dx, y dy if (nx, ny) not in visited: new_dist dist 1 # 只有距离在T范围内的点才需要被记录和继续探索 if new_dist T: visited[(nx, ny)] new_dist queue.append((nx, ny, new_dist))这个写法确保了visited字典里只记录距离在[0, T]之间的点并且队列中不会出现距离大于T的点。3.4 统计结果与复杂度分析当BFS队列为空时visited字典中存储的就是所有在T时刻及之前被染黑的点。字典的大小就是黑点的总数。时间复杂度最坏情况下我们需要访问所有距离源点曼哈顿距离不超过T的点。这些点构成一个复杂的多边形区域。点的数量级大约是O((T * sqrt(N))^2)级别对于BFS来说是可以接受的。使用哈希表使得每次查找和插入的平均时间复杂度为O(1)。空间复杂度主要消耗在visited字典和队列上与需要访问的点数成线性关系。4. 从解题到举一反三BFS解决扩散类问题的模式通过这道国赛题我们可以总结出一套用BFS解决“扩散”、“感染”、“覆盖”类问题的通用方法论。当你下次遇到类似问题时可以按以下步骤思考第一步问题转化与建模确认移动规则通常是上下左右四连通或包括对角线八连通的网格移动。本题是四连通。确认“距离”定义在网格中步数通常等价于曼哈顿距离四连通或切比雪夫距离八连通。本题是曼哈顿距离。判断是否多源初始状态是否有多个起点本题是。理解状态每个网格点就是一个状态。状态是否只取决于位置还是有其他属性如时间、方向等本题状态就是(x, y)坐标。第二步设计BFS核心要素状态表示用什么数据结构表示一个状态本题用(x, y)元组。队列初始化将所有初始状态加入队列并标记其“距离”或“层数”为0。状态扩展根据规则从当前状态可以衍生出哪些新状态本题是向四个方向走一步。判重与剪枝如何判断一个状态是否已被访问过本题用visited字典。哪些状态是无须探索的本题是距离超过T的状态。终止条件BFS何时结束本题有两个条件1) 队列为空自然结束2) 当前处理的状态距离已达到T可以提前停止该分支的扩展但队列可能不空。第三步实现与优化选择合适的数据结构队列、哈希表。注意坐标边界处理本题无限大无需处理越界但某些题有限制。在搜索过程中直接计算或收集答案。第四步测试与验证对于这类题目可以用小数据验证。例如只有一个源点(0,0)T1。那么黑点应该是(0,0),(1,0),(-1,0),(0,1),(0,-1)共5个。手动计算和程序跑出的结果应该一致。5. 常见变体与思路延伸掌握了基础模型我们来看看可能出现的变体这能帮助你在赛场上更灵活地应对。变体一带有阻碍物的扩散如果网格中某些点是障碍物无法被扩散也无法穿过。这需要在BFS扩展时增加一个判断如果扩展到的点是障碍物则不能从该点通过。visited字典也需要记录障碍物状态。这实际上变成了在网格地图上的标准BFS。变体二扩散速度不同如果不是每秒扩散一格而是某些方向或某些区域的扩散速度不同。这可以通过给边赋予不同的“权值”或“代价”来建模。这时BFS就不适用了因为BFS只适用于边权为1的图。需要改用Dijkstra算法如果权值为正来求单源最短路径或者多源Dijkstra。变体三求恰好第T秒新变黑的点本题是求第T秒时所有黑点。如果问题是“第T秒这一秒内新变黑了多少点”那么答案就是visited字典中距离值恰好等于T的点的数量。只需要在BFS过程中或结束后统计dist T的点即可。变体四三维空间扩散原理完全一样只是状态从(x, y)变成了(x, y, z)扩展方向从4个上下左右变成了6个上下左右前后。BFS的代码结构几乎不变只需修改状态表示和方向数组。6. 实战代码与逐行解析下面给出一个Python的参考实现并加上详细注释。我们假设初始点已经给定时间T也已给定。from collections import deque def bfs_diffusion(initial_points, T): 计算在时刻T被扩散覆盖的网格点数量。 :param initial_points: 初始黑点列表例如 [(0,0), (2020,11), (11,14), (2000,2000)] :param T: 时间限制 :return: 被覆盖的点的数量 # 方向数组上下左右 directions [(0, 1), (0, -1), (-1, 0), (1, 0)] # visited字典键为坐标元组(x, y)值为该点被访问时的距离时间 visited {} # 队列元素为 (x, y, distance) queue deque() # 多源BFS初始化所有初始点距离为0入队 for x, y in initial_points: visited[(x, y)] 0 queue.append((x, y, 0)) # 开始BFS while queue: x, y, dist queue.popleft() # 关键优化如果当前点距离已经等于T则从它扩展出的点距离为T1超出限制无需再扩展此点。 # 但队列中其他距离小于T的点仍需处理。 if dist T: continue # 向四个方向扩展 for dx, dy in directions: nx, ny x dx, y dy new_dist dist 1 # 如果新点未被访问过且新距离在T范围内 if (nx, ny) not in visited and new_dist T: visited[(nx, ny)] new_dist queue.append((nx, ny, new_dist)) # visited字典中存储了所有距离在[0, T]之间的点其长度即为答案 return len(visited) # 假设这是题目中的初始点 initial_points [(0, 0), (2020, 11), (11, 14), (2000, 2000)] T 2020 # 假设T2020 result bfs_diffusion(initial_points, T) print(f在时刻 {T}被覆盖的点数为{result})逐行解析与技巧visited使用字典而不是集合是因为我们不仅需要记录点是否被访问还需要记录它是在何时距离被访问的。虽然在本函数最终只用了它的键点坐标但在调试或处理变体问题时记录距离信息很有用。队列中存储了(x, y, dist)。这里dist是冗余的因为可以通过visited[(x, y)]获取。但存储它可以避免每次扩展时都去字典里查询一次对于性能密集型场景如C可能稍有帮助在Python中区别不大但代码更清晰。if dist T: continue这一行是重要的剪枝。它防止了程序去探索那些“即使能到达也已经在时间限制之外”的点减少了不必要的队列操作和字典查询。判断(nx, ny) not in visited和new_dist T的顺序先判断是否访问过再计算新距离和判断范围在逻辑上没问题。但有些写法会先计算新坐标然后判断新距离是否T再判断是否访问过。两种都可以但当前写法更符合“只有可能合格的候选点才去检查是否重复”的直觉。最终答案就是len(visited)。因为visited包含了所有初始点和在扩散过程中被访问到的、距离不超过T的点。这道“扩散”题本质上是一道多源BFS的模板题但其价值在于清晰地揭示了如何将现实世界的“扩散”过程抽象为图论中的最短路径问题。国赛出这样的题意在检验选手的基础算法应用能力和建模思维。记住这个模式下次无论是蓝桥杯还是其他算法竞赛再遇到“扩散”你就能稳稳地拿下。