C语言Flood Fill算法详解及代码实现366

Flood Fill算法是一种图像处理算法，用于将图像中与指定像素颜色相同的区域填充为另一种颜色。它在图像编辑软件、游戏中以及其他图形应用程序中都有广泛的应用。本文将深入探讨C语言实现Flood Fill算法的多种方法，包括递归和迭代两种方式，并分析其优缺点以及适用场景。

一、算法原理

Flood Fill算法的核心思想是递归或迭代地访问与种子像素（起始像素）颜色相同的相邻像素，并将这些像素的颜色更改为新的颜色。算法的终止条件是访问到边界像素（颜色与种子像素不同的像素）或已经访问过的像素。

二、递归实现

递归实现Flood Fill算法简洁明了，易于理解。其基本思路如下：
检查当前像素的颜色是否与目标颜色相同，如果不是，则返回。
将当前像素的颜色更改为新的颜色。
递归调用自身，处理当前像素的四个相邻像素（上、下、左、右）。为了避免死循环，通常需要使用一个visited数组来标记已经访问过的像素。

以下是一个递归实现的C语言代码示例：```c
#include
#define MAX_ROWS 100
#define MAX_COLS 100
int image[MAX_ROWS][MAX_COLS];
int visited[MAX_ROWS][MAX_COLS];
void floodFillRecursive(int row, int col, int oldColor, int newColor) {
if (row < 0 || row >= MAX_ROWS || col < 0 || col >= MAX_COLS ||
visited[row][col] || image[row][col] != oldColor) {
return;
}
visited[row][col] = 1;
image[row][col] = newColor;
floodFillRecursive(row + 1, col, oldColor, newColor);
floodFillRecursive(row - 1, col, oldColor, newColor);
floodFillRecursive(row, col + 1, oldColor, newColor);
floodFillRecursive(row, col - 1, oldColor, newColor);
}
int main() {
// 初始化图像数据，此处省略...
int oldColor = 1; // 需要填充的颜色
int newColor = 2; // 填充后的颜色
int startRow = 5;
int startCol = 5;
floodFillRecursive(startRow, startCol, oldColor, newColor);
// 打印结果，此处省略...
return 0;
}
```

三、迭代实现

递归实现虽然简洁，但存在栈溢出的风险，尤其是在处理大型图像时。迭代实现则可以避免这个问题。常用的迭代方法是使用队列或栈进行广度优先搜索或深度优先搜索。

以下是一个使用队列实现的迭代Flood Fill算法的C语言代码示例：```c
#include
#include
#define MAX_ROWS 100
#define MAX_COLS 100
typedef struct {
int row;
int col;
} Point;
int image[MAX_ROWS][MAX_COLS];
int visited[MAX_ROWS][MAX_COLS];
void floodFillIterative(int row, int col, int oldColor, int newColor) {
Point queue[MAX_ROWS * MAX_COLS];
int head = 0;
int tail = 0;
if (row < 0 || row >= MAX_ROWS || col < 0 || col >= MAX_COLS || image[row][col] != oldColor) return;
queue[tail++] = (Point){row, col};
visited[row][col] = 1;
image[row][col] = newColor;
while (head < tail) {
Point p = queue[head++];
int r = ;
int c = ;
// 检查四个相邻像素
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < MAX_ROWS && nc >= 0 && nc < MAX_COLS &&
!visited[nr][nc] && image[nr][nc] == oldColor) {
visited[nr][nc] = 1;
image[nr][nc] = newColor;
queue[tail++] = (Point){nr, nc};
}
}
}
}
int main() {
// 初始化图像数据，此处省略...
int oldColor = 1;
int newColor = 2;
int startRow = 5;
int startCol = 5;
floodFillIterative(startRow, startCol, oldColor, newColor);
// 打印结果，此处省略...
return 0;
}
```