企业官网建设流程全解析

说真的，Flood Fill（漫水法）和最短路这两个词放在一起，乍看像是两道算法题的缝合怪。但真正做过路径规划、关卡地图处理或者刷过大量网格类算法题的人，应该会有同感：这俩经常成对出现。先用漫水法把二维网格打成若干个连通的“块”，再在这些块之间跑最短路，本质上是把网格问题降维成图论问题，把几十万个格点压成几十个节点。这篇文章就把这套组合讲透，适合算法竞赛选手、游戏后端工程师和日常需要处理网格寻路的开发者。

1. 为什么要将漫水法与最短路组合

1.1 从网格暴力BFS到区域压缩

如果直接在最原始的网格上做最短路，每到一个格子，就要检查四个或者八个邻居。一个一千乘以一千的地图，就是100万个节点，每次查询都要遍历一遍。如果地图是静态的、查询是多次的，这个成本是非常痛的。

Flood Fill解决的第一个问题，就是把地图上所有“互相连通、特性一致”的可通行格子归成同一个组，通常叫连通块或区域。比如一个大房间是一整块，一条走廊是另一块，走廊和房间的连接处就是区域之间的边。等区域划分完，几十万格子变成了几十个区域，节点数量直线下降。之后每次查询，都不用再碰原始大网格，只在区域图上跑最短路就行。

这就像你要判断一个城市里不同地方之间怎么走，不需要把每条街道上的每个路灯都当成一个点，只需要知道每个街区之间有没有路、路况怎么样。网格寻路里的“街区”就是Flood Fill染出来的连通块，“路况”就是区域之间的边权。

1.2 适用场景与收益边界

这套组合不是万能的。它更适合三类场景：

• 地图由大块连续的同质区域组成，比如房间、走廊、草地、沙漠，区域数量远小于格子总数。
• 多次查询，地图不变或很少变化。一次Flood Fill预处理，可以把成本摊到很多次查询上。
• 你真正关心的代价取决于“进入哪种区域”或“穿过多少次边界”，而不是每一个格子一格一格地走。

反过来，如果地图只有少量稀疏障碍，几乎一整块都是连通的，区域数约等于1，压缩本身没有意义。如果只做一次查询，Flood Fill的O(N)遍历加上区域图最短路，往往比直接网格BFS还慢。还有一种情况要特别小心：如果你需要的是精确到每个格子的最短路径长度，简单的区域压缩模型可能失真，因为区域内部的路径长度没有被完整建模。这个坑我在第3章会展开讲。

一句话：区域压缩的价值在“地图结构明确 + 查询次数多”的时候才能体现出来。

2. 漫水法基础实现与易错点

2.1 四连通与八连通的选择

Flood Fill的第一步是确定连通规则。四连通只允许上下左右四个方向扩展；八连通额外允许斜向扩展。这个选择直接影响后续区域图是否正确。

如果你做的游戏或题目只允许上下左右移动，那必须用四连通。如果用八连通来染色，会把斜对角相邻的两个格子划进同一个区域，但实际上角色并不能直接斜穿过去，尤其是墙角位置，八连通会让角色“穿墙”。反过来，如果移动规则确实允许八个方向，那用四连通又会把一个本可以斜穿过去的大区域拆成好几块，区域数量变多，压缩效果变差。

我踩过的一个具体例子是：一个迷宫地图里，两面墙斜对角相抵，中间只有一条缝。四连通下这是两个独立区域，八连通下却会认为它们通过一个角点相连。检查了半天路径才发现是连通规则和移动规则不一致。

2.2 迭代实现与栈/队列细节

递归版Flood Fill写起来很简洁，一行递归就能扩展。但实际地图一大，递归深度很容易破栈。Python默认递归深度只有1000，C++在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(R+E)。
• 边权任意正整数：用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 问题速查表

还有一个特别隐蔽的问题：起点和终点已经在同一个区域时，区域图最短路结果会是0，但真实网格距离不可能是0。如果你要求的是实际步数，这种情况必须在区域内部再做一次BFS。别怪算法，这是模型的选择题。

6.2 性能调优与维护心得

地图静态的情况下，一次Flood Fill预处理可以长期复用，不要每次查询都重新跑。工程上更常见的做法是把区域编号、邻接表序列化保存起来，地图不变就直接加载。

用一维数组保存二维索引时要小心溢出。index = x * width + y在C++里如果x和width都是int，乘积一亿就超过int范围了。很多大图Bug就是这么来的，排查起来非常费劲。建议一开始就用长整型，或者干脆保持二维数组，别为了省那点内存给自己添堵。

我在实际使用中还有一条铁律：写区域图最短路之前，先写一个纯网格暴力BFS当作基准答案，拿小地图对拍。只有暴力答案和区域图答案在小样例上完全一致，才敢上大图。这个问题排查章节里列的错误，几乎都可以用“先对拍，再排查”的方式快速定位，比自己对着代码猜要高效得多。

我实际用这套组合比较久的体会是，它最大的价值不是“加速”，而是把一张密密麻麻的大网格变成一张小而清晰的路由图。你只要把连通块、边权、起点终点所在的块搞清楚，剩下的事情就是教科书最短路。它真正容易写错的地方，几乎都集中在“区域图到底代表什么意思”这一件事上。想清楚这个，代码层面很少出幺蛾子。