★ FEATURED ARTICLE 说真的Flood Fill漫水法和最短路这两个词放在一起乍看像是两道算法题的缝合怪。但真正做过路径规划、关卡地图处理或者刷过大量网格类算法题的人应该会有同感这俩经常成对出现。先用漫水法把二维网格打成若干个连通的“块”再在这些块之间跑最短路本质上是把网格问题降维成图论问题把几十万个格点压成几十个节点。这篇文章就把这套组合讲透适合算法竞赛选手、游戏后端工程师和日常需要处理网格寻路的开发者。1. 为什么要将漫水法与最短路组合1.1 从网格暴力BFS到区域压缩如果直接在最原始的网格上做最短路每到一个格子就要检查四个或者八个邻居。一个一千乘以一千的地图就是100万个节点每次查询都要遍历一遍。如果地图是静态的、查询是多次的这个成本是非常痛的。Flood Fill解决的第一个问题就是把地图上所有“互相连通、特性一致”的可通行格子归成同一个组通常叫连通块或区域。比如一个大房间是一整块一条走廊是另一块走廊和房间的连接处就是区域之间的边。等区域划分完几十万格子变成了几十个区域节点数量直线下降。之后每次查询都不用再碰原始大网格只在区域图上跑最短路就行。这就像你要判断一个城市里不同地方之间怎么走不需要把每条街道上的每个路灯都当成一个点只需要知道每个街区之间有没有路、路况怎么样。网格寻路里的“街区”就是Flood Fill染出来的连通块“路况”就是区域之间的边权。1.2 适用场景与收益边界这套组合不是万能的。它更适合三类场景地图由大块连续的同质区域组成比如房间、走廊、草地、沙漠区域数量远小于格子总数。多次查询地图不变或很少变化。一次Flood Fill预处理可以把成本摊到很多次查询上。你真正关心的代价取决于“进入哪种区域”或“穿过多少次边界”而不是每一个格子一格一格地走。反过来如果地图只有少量稀疏障碍几乎一整块都是连通的区域数约等于1压缩本身没有意义。如果只做一次查询Flood Fill的O(N)遍历加上区域图最短路往往比直接网格BFS还慢。还有一种情况要特别小心如果你需要的是精确到每个格子的最短路径长度简单的区域压缩模型可能失真因为区域内部的路径长度没有被完整建模。这个坑我在第3章会展开讲。场景直接网格最短路Flood Fill 区域最短路大房间走廊多次寻路每次O(N)预处理O(N)查询O(R log R E)R远小于N单次查询的迷宫O(N)够用O(N)O(R log R E)一般更慢不同地形有过路费每格状态转移复杂区域图边权清晰建模自然一句话区域压缩的价值在“地图结构明确 查询次数多”的时候才能体现出来。2. 漫水法基础实现与易错点2.1 四连通与八连通的选择Flood Fill的第一步是确定连通规则。四连通只允许上下左右四个方向扩展八连通额外允许斜向扩展。这个选择直接影响后续区域图是否正确。如果你做的游戏或题目只允许上下左右移动那必须用四连通。如果用八连通来染色会把斜对角相邻的两个格子划进同一个区域但实际上角色并不能直接斜穿过去尤其是墙角位置八连通会让角色“穿墙”。反过来如果移动规则确实允许八个方向那用四连通又会把一个本可以斜穿过去的大区域拆成好几块区域数量变多压缩效果变差。我踩过的一个具体例子是一个迷宫地图里两面墙斜对角相抵中间只有一条缝。四连通下这是两个独立区域八连通下却会认为它们通过一个角点相连。检查了半天路径才发现是连通规则和移动规则不一致。2.2 迭代实现与栈/队列细节递归版Flood Fill写起来很简洁一行递归就能扩展。但实际地图一大递归深度很容易破栈。Python默认递归深度只有1000C在Windows下默认栈空间也不大一张几百乘几百的地图就可能让你直接在递归里崩掉。我建议一律用显式栈或BFS队列实现别在递归上赌运气。一个标准的BFS队列版本长这样from collections import deque def label_regions(grid): h, w len(grid), len(grid[0]) region_id [[-1] * w for _ in range(h)] regions [] dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(h): for j in range(w): if grid[i][j] 0 and region_id[i][j] -1: rid len(regions) regions.append([]) q deque([(i, j)]) region_id[i][j] rid while q: x, y q.popleft() regions[rid].append((x, y)) for dx, dy in dirs: nx, ny x dx, y dy if 0 nx h and 0 ny w: if grid[nx][ny] 0 and region_id[nx][ny] -1: region_id[nx][ny] rid q.append((nx, ny)) return region_id, regions这里的核心细节是入队时立刻标记编号。我见过有人出队时才给格子染色结果同一个格子被重复入队多次染色编号被覆盖区域统计全乱。Flood Fill的访问判断必须和入队动作绑定在一起这一步写错后面所有东西都跟着错。标记方式也有讲究。用独立二维数组region_id保存编号好处是原始地图数据保留不动随时回看某个格子属于哪个区域。直接把原地图原地染色虽然省内存但会让后续调试变得很痛苦因为你再也分不清原来是空地还是障碍物。竞赛里赶时间可以原地改工程项目里我建议老老实实用独立数组。3. 先分区再寻路两段式组合模型3.1 离线预处理阶段Flood Fill 与区域编号组合模型的第一步是离线预处理。遍历整张网格把所有可通行且未编号的格子作为种子执行一次Flood Fill每一次填充产出一个新区域编号。整个流程做完你会得到三类信息region_id每个格子对应的区域编号障碍物保持-1。regions每个区域包含的格子列表或者至少保存代表点和面积。起点和终点分别落在哪个编号里。这个预处理只做一次。地图不变的情况下后续所有最短路查询都建立在区域编号之上。有一个细节容易被忽略起点和终点本身必须属于某个区域。如果起点被墙围死region_id[start]会是-1直接判不可达不用再跑算法。如果起点和终点在同一区域且你要求的只是“能不能到”那答案直接是能到如果你要求真实步数还需要在区域内做一次BFS但这是后话。3.2 构建区域图与边权定义区域编号完成后遍历一遍所有格子检查每个格子的四个邻居。如果邻居的编号不同说明这两个区域之间存在一条边界。把所有边界收集起来就能构建区域邻接图。重复边要处理。一个大区域和另一个大区域可能共享很长一段边界按格子扫过去会生成大量重复的邻接关系。我习惯用dict存最小边权或者先放到set里再去重避免最终图上出现一堆冗余边。from collections import defaultdict def build_region_graph(region_id): h, w len(region_id), len(region_id[0]) adj defaultdict(dict) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] for x in range(h): for y in range(w): if region_id[x][y] -1: continue for dx, dy in dirs: nx, ny x dx, y dy if 0 nx h and 0 ny w: ra, rb region_id[x][y], region_id[nx][ny] if ra ! -1 and rb ! -1 and ra ! rb: # w 根据题目或业务定义这里先假设跨区域一步代价为 1 if 1 adj[ra].get(rb, 10**9): adj[ra][rb] 1 if 1 adj[rb].get(ra, 10**9): adj[rb][ra] 1 return adj这里最关键的问题来了边权到底应该设成什么有一种情况边权设成1就够了。你求的目标是“最少穿越几个区域”本质是最小化跨区次数。比如某些关卡问题里每进入一个新区域就需要消耗一张通行证此时边权设成1是正确且自然的。但如果你求的是网格上的真实最短步数问题就没这么简单了。区域内部的路径长度完全被压缩掉了一个区域内部从东走到西可能要走500步压缩成节点后这部分步数在图上根本体现不出来。这时候直接对区域图跑最短路结果一定偏小甚至完全错误。要解决这个问题有两种方案。第一种是抛弃“区域节点”的简化模型改成“端口模型”把每个区域和邻居区域的交界处抽象成端口节点用区域内BFS或距离场预先算出同一区域里不同端口之间的最短距离再在端口图上跑最短路。第二种是在业务允许时干脆把区域本身当成均匀的“价格标签”边权定义为进入目标区域的额外代价最终求的是带权跨区路径。我实际接触到的“Flood Fill 最短路”题目大多数用的是第二种简化模型。做题或设计方案之前一定要先问自己优化目标是跨区代价还是真实步数这个问题不搞清楚后面调再久也是白费。4. 最短路求解与原路径恢复4.1 用什么最短路算法区域图建好之后剩下的就是教科书最短路。选什么算法取决于边权边权全是1直接普通BFS又快又简单。边权只有0和1用0-1 BFS双端队列维护复杂度O(RE)。边权任意正整数用Dijkstra堆优化版本稳定可靠。边权存在负数尽量别用除非特殊题目有负环处理否则不推荐。一般区域图规模不大Dijkstra是最省心的选择。代码框架也很固定import heapq def dijkstra(adj, start, target, n): INF 10**18 dist [INF] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d ! dist[u]: continue if u target: break for v, w in adj[u].items(): nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist[target] if dist[target] ! INF else -1如果地图有多个起点比如一个大厅有多个入口想把任意一个入口到目标区域的最短路算出来做法也很简单把所有起点的距离都初始化为0全部塞进优先队列一次Dijkstra就能跑完。这比每个起点单独跑一遍省非常多。4.2 路径还原与坐标映射只输出最短距离的时候区域图最短路很好用。但如果你需要一条能走的实际路径麻烦就来了算法跑出来的是区域编号序列比如“区域3 - 区域7 - 区域9”这不是一个个格子坐标没法直接拿来用。解决办法是分两步。第一步在Dijkstra里记录前驱节点拿到区域序列。第二步在Flood Fill阶段顺便给每个区域保存一个代表点比如第一次染色的种子格还需要在构建邻接边时记录这条边对应的一对边界格子坐标。当区域序列确定后依次把相邻区域通过边界点衔接起来再在单个区域内部补一段局部BFS路径就能拼出一条完整的网格路径。这个工作确实繁琐但实际项目中往往无法跳过去。我的建议是不要在区域内部也完全省略路径而是用“区域序列做剪枝、局部网格BFS做细节”的方式还原既快又准确。5. 实战场景与算法变形5.1 迷宫与障碍寻路的地形代价模型最经典的场景是不同地形带不同通行代价。想象一张迷宫地图里面有平原、沼泽和山地进入平原消耗1点体力进入沼泽消耗3点进入山地消耗5点墙不可通行。起点在平原某处终点在山地某处你想知道最小体力消耗。直接做法是在每个格子上扩展状态边权随进入的地形而变化等于每个格子都判断一次地形类型网格一大就非常慢。用Flood Fill的思路就不一样先把所有连通的平原块染色成区域沼泽和山地也被染成各自的连通块。由于同一块区域内地形类型相同区域图的边权可以直接定义为“进入目标区域需要消耗的体力”然后跑一次Dijkstra得到的就是最小体力消耗路径。这个模型在题目里经常出现它的精髓在于区域内部的地形是均匀的代价只发生在跨区域的那一刻。反过来说如果地形在同一个连通块内部都不均匀那Flood Fill的“同质区域”假设就不成立了需要先按地形颜色再做一次区域细分。5.2 图像分割、扫地机器人与更多扩展跳出刷题场景这套组合在其他领域的应用也很广。图像处理里的连通域标记本身就是Flood Fill。先对二值图像做连通域染色每个连通域是一个对象如果再在这些对象之间构造连通关系可以解决“两个目标区域是否相邻”“最贴近的两个区域边界在哪”这类问题。区域数量通常比像素数量少很多后续计算量非常可控。扫地机器人的路径规划也常用这套思路。先把室内地图按房间、走廊分割成若干连通区域每个区域内部做一次局部清扫路径规划再在区域连通图上决定清扫顺序。如果直接在整张高分辨率栅格地图上搜索覆盖路径计算量会非常夸张区域化之后搜索空间骤然缩小。游戏地图里的A*寻路同样可以借助Flood Fill做预处理。先判断起点和终点是否在同一个连通块如果中间被墙完全隔开直接返回不可达省去一次昂贵的寻路搜索。如果起点终点可到达先用区域图跑一个粗略路径再沿着区域边界细化能让高频寻路的开销大幅下降。还有一个我常提的例子是扫雷点开空白格子时Flood Fill会自动向四周展开所有相邻的零区域这其实就是漫水法在交互逻辑里的日常应用。6. 常见问题与排查实录6.1 问题速查表现象大概率原因处理方式递归程序跑到一半崩溃地图太深递归栈溢出改用显式栈或BFS队列区域编号超过255后行为异常存储编号用了char或uint8改成int路径明明不该穿墙却穿过去了用了八连通染色允许斜穿墙角按移动规则改四连通最短路结果和手算对不上边权建模错误比如把穿越区域次数当成了真实步数重新确认优化目标起点终点可走但返回不可达起点或终点在墙中region_id为-1先检查起点终点所在区域同一对区域之间出现大量重复边构建邻接时没去重或没取最小边权用set或dict合并Dijkstra结果没有预期的快区域图过大或边权建错导致边膨胀检查重复边合并是否做好还有一个特别隐蔽的问题起点和终点已经在同一个区域时区域图最短路结果会是0但真实网格距离不可能是0。如果你要求的是实际步数这种情况必须在区域内部再做一次BFS。别怪算法这是模型的选择题。6.2 性能调优与维护心得地图静态的情况下一次Flood Fill预处理可以长期复用不要每次查询都重新跑。工程上更常见的做法是把区域编号、邻接表序列化保存起来地图不变就直接加载。用一维数组保存二维索引时要小心溢出。index x * width y在C里如果x和width都是int乘积一亿就超过int范围了。很多大图Bug就是这么来的排查起来非常费劲。建议一开始就用长整型或者干脆保持二维数组别为了省那点内存给自己添堵。我在实际使用中还有一条铁律写区域图最短路之前先写一个纯网格暴力BFS当作基准答案拿小地图对拍。只有暴力答案和区域图答案在小样例上完全一致才敢上大图。这个问题排查章节里列的错误几乎都可以用“先对拍再排查”的方式快速定位比自己对着代码猜要高效得多。我实际用这套组合比较久的体会是它最大的价值不是“加速”而是把一张密密麻麻的大网格变成一张小而清晰的路由图。你只要把连通块、边权、起点终点所在的块搞清楚剩下的事情就是教科书最短路。它真正容易写错的地方几乎都集中在“区域图到底代表什么意思”这一件事上。想清楚这个代码层面很少出幺蛾子。
阅读完成 · 觉得有帮助？
