初识 Floodfall 算法

---

一、Floodfall 算法的概述

Floodfall 算法通常用于解决与区域填充、图的遍历等相关的问题。它的中文名字：洪水灌溉，顾名思义它的核心思想是从一个起始点开始，像洪水一样蔓延，直到满足特定的条件或覆盖整个目标区域。

Floodfall 算法在实现过程中，常常会基于深度优先搜索（DFS）和广度优先搜索（BFS）的思想。

二、深度优先搜索（DFS）和广度优先搜索（BFS）在 Floodfall 算法中的应用

深度优先搜索（DFS）在 Floodfall 算法中，会沿着一条路径尽可能深地探索下去，直到无法继续，然后回溯。这种方式在某些情况下能够快速找到较深的区域，但可能会忽略一些较近但隐藏较深的区域。

例如，在一个迷宫中，如果使用 DFS 进行 Floodfall 式的探索，可能会先深入一条复杂的长通道，而错过一些就在入口附近但需要绕一点路才能到达的区域。

广度优先搜索（BFS）则是逐层地向外扩展，先访问距离起始点近的节点，再逐步扩展到更远的节点。在 Floodfall 算法中，BFS 能确保先填充距离起始点较近的区域，填充的顺序更加有序和可预测。

比如在地图填充中，使用 BFS 进行 Floodfall 操作，会先填充起始点周围的区域，再逐渐向外扩散。

三、算法的基本原理

Floodfall 算法一般会使用某种数据结构（如队列或栈）来存储待处理的节点。从起始节点出发，将其相邻的未访问节点加入数据结构，然后依次处理这些节点，不断扩展填充区域。

四、应用场景

1. 图像处理中的颜色填充。
2. 游戏地图中的区域探索。

下面是一个使用 C++实现的简单 Floodfall 算法示例代码，用于填充二维矩阵中的一个区域，分别展示了基于 DFS 和 BFS 的实现方式：

#include <iostream>
#include <stack>
#include <queue>// 定义矩阵的大小
const int ROWS = 10;
const int COLS = 10;// 方向数组，用于遍历相邻节点
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };// 定义一个结构体来表示节点
struct Node {int x;int y;
};// 基于 DFS 的 FloodFill 函数
void floodFillDFS(int grid[ROWS][COLS], int startX, int startY, int targetColor, int newColor) {std::stack<Node> s;Node start;start.x = startX;start.y = startY;s.push(start);while (!s.empty()) {Node curr = s.top();s.pop();int x = curr.x;int y = curr.y;// 如果当前节点的颜色与目标颜色不同，跳过if (grid[x][y]!= targetColor) {continue;}// 更改颜色grid[x][y] = newColor;// 遍历相邻节点for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界if (newX >= 0 && newX < ROWS && newY >= 0 && newY < COLS) {Node next;next.x = newX;next.y = newY;s.push(next);}}}
}// 基于 BFS 的 FloodFill 函数
void floodFillBFS(int grid[ROWS][COLS], int startX, int startY, int targetColor, int newColor) {std::queue<Node> q;Node start;start.x = startX;start.y = startY;q.push(start);while (!q.empty()) {Node curr = q.front();q.pop();int x = curr.x;int y = curr.y;// 如果当前节点的颜色与目标颜色不同，跳过if (grid[x][y]!= targetColor) {continue;}// 更改颜色grid[x][y] = newColor;// 遍历相邻节点for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界if (newX >= 0 && newX < ROWS && newY >= 0 && newY < COLS) {Node next;next.x = newX;next.y = newY;q.push(next);}}}
}// 打印矩阵
void printGrid(int grid[ROWS][COLS]) {for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {std::cout << grid[i][j] << " ";}std::cout << std::endl;}
}int main() {int grid[ROWS][COLS] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 1, 0},{0, 1, 0, 1, 1, 1, 1, 0, 1, 0},{0, 1, 0, 1, 0, 0, 1, 0, 1, 0},{0, 1, 0, 1, 0, 0, 1, 0, 1, 0},{0, 1, 0, 1, 1, 1, 1, 0, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 1, 0},{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};std::cout << "原始矩阵：" << std::endl;printGrid(grid);std::cout << "基于 DFS 填充后的矩阵：" << std::endl;floodFillDFS(grid, 1, 1, 1, 2);printGrid(grid);std::cout << "基于 BFS 填充后的矩阵：" << std::endl;floodFillBFS(grid, 1, 1, 2, 3);printGrid(grid);return 0;
}

在上述代码中，我们分别实现了基于 DFS 和 BFS 的 Floodfall 算法，用于填充二维矩阵中的指定区域。