🌊 图论算法

画图软件里的「油漆桶」为什么点一下就把整片颜色都换了？扫雷为什么一点空白就翻开一大片？围棋怎么判断该不该「提子」？答案都藏在一个会「像水一样漫开」的算法里——泛洪算法（flood fill）。

考纲知识点：图的泛洪算法（floodfill）

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 七级

(3) 为考纲同一条目，同束图的定义及遍历与图论算法两知识块

(3)图的定义及基本图论算法。包括图的定义、图的种类（有向图、无向图），图节点的度的概念。掌握编程时图的数据结构表示，以及基于深度优先搜索（DFS）和广度优先搜索（BFS）的图搜索与遍历方法，图的泛洪（floodfill）算法。

📚

先学一学

花 5 分钟读完下面 4 课，再去闯关就不慌啦

💧 泛洪算法：像水一样漫开

在一张地图上，如果有一个格子被「选中」，把和它连在一起、满足同样条件的格子全部找出来、一起处理，就像把水倒下去让它自动流满整个洼地——这个算法叫泛洪算法（Flood Fill）。它找出来的是一整块「连通区域」。

🎨 画图软件的油漆桶

「油漆桶」点一下封闭区域，整片同色区域就变颜色。电脑其实是从你点的那个格子出发，把周围颜色相同的格子一路「漫」过去，全都刷上新颜色。

💡 口诀：泛洪 = 倒一桶水，让它自己流满连通的小洼地。

💣 扫雷的大招

扫雷里点到空白格，会「哗」一下翻开一大片——因为空白格向四周扩散，碰到数字才停。这正是泛洪：从空白格出发，把连成片的空白全翻出来。

🧭 往哪几个方向扩散：四连通和八连通

水能往哪流，要先规定好方向：

🔄 两种连通方式

· 四连通：只能往上、下、左、右四个方向走（像「十」字）。

· 八连通：四方向再加左上、右上、左下、右下四个斜角（像「米」字）。

💡 口诀：四连通走「十」字，八连通走「米」字；选哪种看题目，别把斜角算错。

🪪 每块都要「登记过」

泛洪时最重要的是标记访问：每个格子一旦被淹过就记下来，下次不再进去，否则会在连通区域里绕圈圈停不下来。

🧪 泛洪就是「从起点出发的搜索」

泛洪算法本质上是在做从起点出发的 DFS 或 BFS：只是「往哪走」的判断条件变成了「颜色一样 / 是空地 / 没来过」。所以泛洪既可以用 DFS 实现，也可以用 BFS 实现。

🧪 读代码：递归 DFS 版的泛洪

看得懂就好，不用背：每到一个格子先标记，再上下左右试邻居。

void dfs(int x, int y) {
  vis[x][y] = true;
  for (int k = 0; k < 4; k++) {
    int nx = x + dx[k], ny = y + dy[k];
    if (inside(nx, ny) && !vis[nx][ny])
      dfs(nx, ny);
  }
}

注意：如果地图很大、连通区域很深，递归一层套一层可能把调用栈撑爆，程序直接崩溃。

💡 口诀：泛洪 = 起点出发的搜索；小图递归 DFS，大图换 BFS 用队列。

🛡️ 大地图怎么办：改用 BFS

大的二维地图里，一般不用递归，而是改用BFS + 队列：把要淹的格子排进队列，一个个处理。队列放在内存的「堆」上，不像函数调用那样一层层压栈，能处理更大面积。工程里的大图 flood fill 基本都是这么干的。

⚫ 围棋、连通块与更多应用

泛洪还能帮我们判断「一块棋有没有气」，以及「地图上有几块连在一起的区域」。

⚫ 围棋里的泛洪

围棋中一块棋的「气」是和它相邻的空点。落下一枚棋子后要不要提掉对方的子，可以用泛洪：从对方的某颗子开始扩散，如果能一路沿着空格「漫」到外面的气，说明它还有气；如果整块都被围住、扩散不到任何空点，就没气了，可以提子。

💡 口诀：围棋提子看有没有气，泛洪沿空格一漫就知道。

🗺️ 数一数有几块陆地

给一张 0/1 地图，1 是陆地。想数有几块分开的陆地，就一遍遍泛洪：碰到一块没去过的新陆地就「淹」一次、计数器 +1，直到整张图没有漏网的陆地。图像处理里找「连通区域」、做区域分割，也用同样思路。

🎯

闯关小锦囊 · 考点提醒

泛洪算法 flood fill：从起点出发，把连在一起、条件相同的格子全部找出来并处理。
泛洪本质上就是从起点出发的 DFS/BFS 搜索：既可用 DFS，也可用 BFS 实现。
四连通只走上/下/左/右；八连通还能走四个斜角。
一定要标记访问（visited），否则会在连通区域里绕圈。
递归 DFS 泛洪在大的地图里容易栈溢出；大地图一般改用 BFS + 队列。
应用：画图「油漆桶」填色、扫雷翻开空白区、围棋判断提子、数连通块、图像区域分割。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。