Flood Fill 算法——大自然的智慧

头图为成都锦城湖畔，与本文内容无关。

Flood Fill 算法——大自然的智慧#

$Once~upon~a~time$ ，在这个世界的某个角落，生活这一个人。祂喜欢田园般宁静的生活、还有OI。每至假期，祂便会扳着自己的小笔记本回到乡下老家，开始祂的内卷生活。

这天，下起了大雨，祂一如既往的坐在屋中刷题。这是一道搜索题，要求求出地图中连通块的个数。可是祂没学过BFS和DFS，冥思苦想了一会，祂变得比较烦躁。一缕阳光透过窗帘，照在祂紧握鼠标的右手上——雨停了，此时祂意识到，是时候放松一下自我，出门去转悠转悠了……

雨后的田地无比清香，雨珠垂挂在苇叶上，倒映着绿草蓝天……但是此时，祂一脚踩进了盛满泥水的土坑里，原本愉悦的心情瞬间化为乌有。泥水泼溅出去，流进了祂方才踩出的泥脚印里。看到这一幕，祂陷入了沉思，短短的两分钟后，祂似乎想到了什么，冲进屋里、打开电脑，又开始码起字来了……

~~以上纯属虚构~~

这段故事从某种角度上揭示了Flood Fill算法的基本工作原理——将深度相同的节点染上相同颜色。如同自然界中的洪水，总是从始发地开始，优先向海拔低于始发地的地点扩散，因此更高的地方就不会被淹没，自然也就不会被染色。在扫雷游戏中，消除无地雷的连通块也是基于这个原理实现的；而在画图软件中，填充颜色桶的实现也是这个原理（它甚至还是C语言中的一个函数）。

Flood Fill 算法实现#

对于连通块的处理，分两种情况——四连通和八连通。前者将斜方向的四个方块判定为不连通、后者则是将某方块周围围绕的八个方块全部看作连通。如下图所示：

（其中判定为与棕色方块连通的方块用绿色标出）

实现细节就是：在搜索下一个方块时，先判断是否连通，若连通则在该点进行 Flood Fill 算法。用DFS（递归）和BFS（队列）均可实现该算法。

DFS版：

1
int matrix[N][N];
2
bool vis[N][N];
3
int n;
4

5
void floodfill(int x, int y, int color, int old_color) {
6
    if (1 <= x <= n && 1 <= y <= n && !vis[x][y] && matrix[x][y] == old_color) {
7
        vis[x][y] = true;
8
        matrix[x][y] = color;
9
        // 四连通
10
        floodfill(x + 1, y, color, old_color);
11
        floodfill(x, y + 1, color, old_color);
12
        floodfill(x - 1, y, color, old_color);
13
        floodfill(x, y - 1, color, old_color);
14
        // 八连通
15
//        floodfill(x + 1, y + 1, color, old_color);
16
//        floodfill(x + 1, y - 1, color, old_color);
17
//        floodfill(x - 1, y + 1, color, old_color);
18
//        floodfill(x - 1, y - 1, color, old_color);
19
    }
20
}

BFS版：

1
struct Point {
2
    int x, y, color;
3
};
4

5
int matrix[N][N];
6
bool vis[N][N];
7
queue<Point> q;
8
int n;
9

10
void floodfill(int x, int y, int color, int old_color) {
11
    while (!q.empty()) {
12
        Point p = q.front();
13
        q.pop();
14
        if (1 <= p.x <= n && 1 <= p.y <= n && !vis[p.x][p.y] && p.color == old_color) {
15
            vis[p.x][p.y] = true;
16
            matrix[p.x][p.y] = color;
17
            // 四连通
18
            q.push((Point) {x + 1, y, matrix[x + 1][y]});
19
            q.push((Point) {x, y + 1, matrix[x][y + 1]});
20
            q.push((Point) {x - 1, y, matrix[x - 1][y]});
21
            q.push((Point) {x, y - 1, matrix[x][y - 1]});
22
            // 八连通
23
//            q.push((Point) {x + 1, y + 1, matrix[x + 1][y + 1]});
24
//            q.push((Point) {x + 1, y - 1, matrix[x + 1][y - 1]});
25
//            q.push((Point) {x - 1, y + 1, matrix[x - 1][y + 1]});
26
//            q.push((Point) {x - 1, y - 1, matrix[x - 1][y - 1]});
27
        }
28
    }
29
}

两端代码均实现将连通块内的数字更改为另一个数字的功能。

洛谷 P1596 [USACO10OCT] Lake Counting S#

题目传送门：P1596

题目难度：普及-

题目来源：USACO 2010

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\leq N\leq 100, 1\leq M\leq 100)$ 的网格图表示。每个网格中有水（W）或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
输入输出：
输入第 $1$ 行：两个空格隔开的整数：和。
第 $2$ 行到第行：每行个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。
输出一行，表示水坑的数量。
样例输入 #1
1
10 12
2
W........WW.
3
.WWW.....WWW
4
....WW...WW.
5
.........WW.
6
.........W..
7
..W......W..
8
.W.W.....WW.
9
W.W.W.....W.
10
.W.W......W.
11
..W.......W.
样例输出 #1
1
3

Flood Fill 裸题，题目要求简化为输出由字符 $W$ 组成的连通块的总数，即可套用模板求解。

代码：

1
#include <bits/stdc++.h>
2

3
#define N 110
4
using namespace std;
5

6
struct Point {
7
    int x, y;
8
};
9

10
int n, m;
11
char matrix[N][N];
12
bool vis[N][N];
13
queue<Point> q;
14

15
void floodfill(char color, char old_color) {
16
    while (!q.empty()) {
17
        Point p = q.front();
18
        q.pop();
19
        if (!vis[p.x][p.y] && 1 <= p.x <= n && 1 <= p.y <= m && matrix[p.x][p.y] == old_color) {
20
            vis[p.x][p.y] = true;
21
            matrix[p.x][p.y] = color;
22
            for (int i = p.x - 1; i <= p.x + 1; i++) {
23
                for (int j = p.y - 1; j <= p.y + 1; j++) {
24
                    q.push((Point) {i, j});
25
                }
26
            }
27
        }
28
    }
29
}
30

31
int main() {
32
    ios::sync_with_stdio(false);
33
    cin.tie(nullptr);
34
    cout.tie(nullptr);
35

36
    cin >> n >> m;
37
    for (int i = 1; i <= n; i++) {
38
        for (int j = 1; j <= m; j++) {
39
            cin >> matrix[i][j];
40
        }
41
    }
42
    int ans = 0;
43
    for (int i = 1; i <= n; i++) {
44
        for (int j = 1; j <= m; j++) {
45
            if (matrix[i][j] == 'W' && !vis[i][j]) {
46
                q.push((Point) {i, j});
47
                floodfill('.', 'W');
48
                ans++;
49
            }
50
        }
51
    }
52
    cout << ans << endl;
53
    return 0;
54
}

总用时： ${34ms}$ 记录

洛谷 P3456 [POI 2007] GRZ-Ridges and Valleys#

题目传送门：P3456

题目难度：普及+/提高

题目来源：POI 2007

给定一个地图，为小朋友想要旅行的区域，地图被分为n*n的网格，每个格子(i,j) 的高度w(i,j)是给定的。若两个格子有公共顶点，那么他们就是相邻的格子。（所以与(i,j)相邻的格子有(i-1, j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)）。我们定义一个格子的集合S为山峰（山谷）当且仅当：
1.S的所有格子都有相同的高度。
2.S的所有格子都联通3.对于s属于S，与s相邻的s’不属于S。都有ws > ws’（山峰），或者ws < ws’（山谷）。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。
输入第一行包含一个正整数n，表示地图的大小（1<=n<=1000）。接下来一个n*n的矩阵，表示地图上每个格子的高度。(0<=w<=1000000000)
输出应包含两个数，分别表示山峰和山谷的数量。
感谢@Blizzard 提供的翻译
输入输出：
输入的第一行，为一个整数 $n$ （ ${2\leq n\leq1000}$ ）。
接下来 $n$ 行，每行 $n$ 个数字，为高程图
输出仅一行，分别是地图中山峰和山谷的总数，用空格分开。
样例输入 #1：
1
5
2
8 8 8 7 7
3
7 7 8 8 7
4
7 7 7 7 7
5
7 8 8 7 8
6
7 8 8 8 8
样例输出 #1
1
2 1

显然山峰山谷只能是在同一高度上的连通块，在输入里体现为由同一数字组成的连通块。不难发现，这个题目是一个八连通问题。

整体思路架构在 Flood Fill 算法的基础上，只是我们需要对当前方块的连通方块进行高度判断，以确定该高度上的连通块是否是山峰或者山谷。考虑当 BFS 扫到的点的高度与当前连通块高度不同时，进行判断——如果周边存在一个连通方块，并且这个扩展方块的高度高于当前的方块，那么当前连通块显然不可能是山峰，反之亦然。

代码（这个题卡 queue，建议手写队列）：

1
#include <bits/stdc++.h>
2
#define N 3010
3
#define x first
4
#define y second
5
using namespace std;
6

7
typedef long long ll;
8

9
typedef pair<int, int> Point;
10
int n;
11
int g[N][N];
12
bool vis[N][N];
13
Point q[N * N];
14

15
void floodfill(int x, int y, bool &not_peak, bool &not_valley) {
16
  q[0] = (Point) {x, y};
17
  int hh = 0, tt = 0;
18
  while (hh <= tt) {
19
    Point p = q[hh++];
20
    vis[p.x][p.y] = true;
21
    for (int i = p.x - 1; i <= p.x + 1; i++) {
22
      for (int j = p.y - 1; j <= p.y + 1; j++) {
23
        if (i == p.x && j == p.y) continue;
24
        if (0 <= i && i < n && 0 <= j && j < n) {
25
          if (g[i][j] != g[p.x][p.y]) {
26
            if (g[i][j] < g[p.x][p.y]) not_valley = true;
27
            else not_peak = true;
28
          } else if (!vis[i][j]) {
29
            //q.push((Point) {i, j});
30
            q[++tt] = (Point) {i, j};
31
          }
32
        }
33
      }
34
    }
35
  }
36
}
37

38
int main() {
39
  ios::sync_with_stdio(false);
40
  cin.tie(nullptr);
41
  cout.tie(nullptr);
42

43
  cin >> n;
44
  for (int i = 0; i < n; i++) {
45
    for (int j = 0; j < n; j++) {
46
      cin >> g[i][j];
47
    }
48
  }
49

50
  int peak = 0, valley = 0;
51
  for (int i = 0; i < n; i++) {
52
    for (int j = 0; j < n; j++) {
53
      if (!vis[i][j]) {
54
        bool npeak = false, nvalley = false;
55
        floodfill(i, j, npeak, nvalley);
56
        if (!npeak) peak++;
57
        if (!nvalley) valley++;
58
      }
59
    }
60
  }
61

62
  cout << peak << ' ' << valley << endl;
63
  return 0;
64
}

总用时： ${386ms}$ 记录

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

Flood Fill 算法——大自然的智慧

Flood Fill 算法——大自然的智慧#

Flood Fill 算法实现#

洛谷 P1596 [USACO10OCT] Lake Counting S#

洛谷 P3456 [POI 2007] GRZ-Ridges and Valleys#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

Flood Fill 算法——大自然的智慧

Flood Fill 算法——大自然的智慧#

Flood Fill 算法实现#

洛谷 P1596 [USACO10OCT] Lake Counting S#

洛谷 P3456 [POI 2007] GRZ-Ridges and Valleys#

支持与分享

评论区

音乐

目录

JustPureH₂O