一、课上练习

编程练习

1. 细胞数量: L3361

二、知识总结

✨ 核心思想

泛洪算法（Flood Fill Algorithm），也被称为种子填充算法，是一种用于确定连续区域内像素点的颜色或标记的算法。它主要用在计算机图形中，比如在图像编辑软件中实现"填充"工具，或者在计算机游戏中用于区域检测。泛洪算法可以被看作是图数据结构中的广度优先搜索（BFS）或深度优先搜索（DFS）的应用。

✨ 算法原理

泛洪算法从一个给定的起点（种子点）开始，探索所有相邻的、颜色相同的像素点，并将它们更改为新的颜色。这个过程持续进行，直到所有与种子点连通的、具有相同初始颜色的像素点都被重新上色。

✨ 算法步骤

泛洪算法的执行步骤如下：

1. 选择种子点：确定开始填充的起始像素点。
2. 检查相邻像素：查看种子点的四个或八个邻近像素（基于四连通或八连通邻域）。
3. 判定条件：如果相邻像素的颜色与起始像素的原始颜色相同，将其颜色更改为新颜色。
4. 递归或迭代：对所有符合条件的相邻像素点重复执行上述过程。
5. 终止条件：当没有更多符合条件的相邻像素时，算法停止。

✨ 实现方法

泛洪算法可以通过递归实现（DFS 风格）或使用队列实现（BFS 风格）。递归实现简单但容易导致栈溢出，特别是在处理大区域时。使用队列的实现可以有效避免这个问题。

✨ 执行示例

下面用一个具体的矩阵，完整展示泛洪算法的执行过程。

示例矩阵（5x5）： 1 表示陆地，0 表示水

1 1 0 0 1
1 0 0 1 1
0 0 1 1 0
0 0 0 0 0
1 1 0 1 1

目标： 统计连通区域（岛屿）的数量。

执行过程（使用 DFS，四连通）：

第 1 次扫描： 找到 matrix[0][0]=1 且未访问

• 开始 DFS(0,0)，标记 visited[0][0]=true
  • DFS(0,1)：matrix[0][1]=1，标记 visited
  • 上越界、右 matrix[0][2]=0 跳过、下 matrix[1][1]=0 跳过、左已访问
  • DFS(1,0)：matrix[1][0]=1，标记 visited
  • 上已访问、右 matrix[1][1]=0 跳过、下 matrix[2][0]=0 跳过、左越界
• 第 1 个连通区域：{(0,0), (0,1), (1,0)}，计数 count=1

第 2 次扫描： 继续扫描，找到 matrix[0][4]=1 且未访问

• DFS(0,4) -> DFS(1,4) -> DFS(1,3) -> DFS(2,3) -> DFS(2,2)
• 第 2 个连通区域：{(0,4), (1,4), (1,3), (2,3), (2,2)}，count=2

第 3 次扫描： 找到 matrix[4][0]=1 且未访问

• DFS(4,0) -> DFS(4,1)
• 第 3 个连通区域：{(4,0), (4,1)}，count=3

第 4 次扫描： 找到 matrix[4][3]=1 且未访问

• DFS(4,3) -> DFS(4,4)
• 第 4 个连通区域：{(4,3), (4,4)}，count=4

最终结果： 共有 4 个连通区域。

✨ 解题步骤详解

以"细胞数量"为例，展示泛洪算法的解题流程：

问题： 给定一个 n*m 的矩阵，0 表示空，非 0 表示有细胞。连通的细胞属于同一个细胞团。求细胞团数量。

解题步骤：

1. 读入矩阵：将矩阵存入二维数组。
2. 初始化 visited 数组：全部设为 false。
3. 双重循环扫描：遍历每个格子 (i, j)。
4. 发现新区域：如果 matrix[i][j] != 0 且 visited[i][j] == false，说明找到了一个新的连通区域：
   • count++
   • 从 (i, j) 开始执行 DFS 或 BFS，将所有与之连通的非零格子标记为 visited
5. DFS/BFS 的方向：
   • 四连通：上下左右 4 个方向，dx={-1,0,1,0}，dy={0,1,0,-1}
   • 八连通：加上四个对角方向，共 8 个方向
6. 边界检查：每次移动前检查新坐标是否在矩阵范围内。
7. 输出 count。

BFS vs DFS 的选择：

• DFS 实现简单（递归），但大矩阵可能栈溢出
• BFS 用队列实现，不会栈溢出，适合大数据量

✨ 常见错误

1. 四连通和八连通搞混：有些题目只考虑上下左右四个方向相邻，有些还包括对角线。仔细审题确定连通方式。
2. 边界检查遗漏：移动到新坐标 (nx, ny) 前必须检查 nx >= 0 && nx < n && ny >= 0 && ny < m，否则会数组越界。
3. DFS 递归过深导致栈溢出：当矩阵很大（如 1000*1000）且全是 1 时，DFS 递归深度可达 100 万，会导致栈溢出。解决方案：使用 BFS，或手动增大栈空间。
4. 忘记在入队/递归前检查 visited：不检查会导致同一个格子被多次处理，效率极低甚至死循环。
5. 修改原矩阵代替 visited 数组：虽然可以通过将访问过的 1 改为 0 来省去 visited 数组，但这会破坏原始数据。如果后续还需要使用原矩阵，应该使用独立的 visited 数组。

下面的代码同时演示了 DFS 和 BFS 两种实现方式，用于统计矩阵中连通区域的数量：

1#include<iostream>
2#include<queue>
3using namespace std;
4
5int matrix[55][55] = {0};
6bool visited[55][55] = {0};
7int dx[4] = {-1, 0, 1, 0};
8int dy[4] = {0, 1, 0, -1};
9
10void dfs(int x, int y, int n, int m) {
11    visited[x][y] = true;
12    for (int i = 0; i < 4; i++) {
13        int nx = x + dx[i];
14        int ny = y + dy[i];
15        if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] == 1 && !visited[nx][ny]) {
16            dfs(nx, ny, n, m);
17        }
18    }
19}
20
21struct Point{
22    int x;
23    int y;
24};
25
26void bfs(int x, int y, int n, int m){
27    queue<Point>q;
28    Point start = {x, y};
29    q.push(start);
30    visited[x][y] = true;
31    while (!q.empty()) {
32        Point point = q.front();
33        q.pop();
34        for (int i = 0; i < 4; i++) {
35            int nx = point.x + dx[i];
36            int ny = point.y + dy[i];
37            if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] == 1 && !visited[nx][ny]) {
38                visited[nx][ny] = true;
39                q.push(Point{nx, ny});
40            }
41        }
42    }
43}
44
45int main() {
46    int n = 0;
47    int m = 0;
48    cin >> n >> m;
49    for (int i = 0; i < n; i++) {
50        for (int j = 0; j < m; j++) {
51            cin >> matrix[i][j];
52        }
53    }
54    int result = 0;
55    for (int i = 0; i < n; i++) {
56        for (int j = 0; j < m; j++) {
57            if (matrix[i][j] == 1 && !visited[i][j]) {
58                result++;
59                dfs(i, j, n, m);
60                bfs(i, j, n, m);
61            }
62        }
63    }
64    cout << result << endl;
65    return 0;
66}

三、课后练习

编程练习

1. The Castle: L3362