C语言如何实现Floodfill算法？-C语言-盈思创科技

什么是Flood Fill算法？

Flood Fill，又称种子填充，是一种在图形学中广泛使用的算法，它的作用是从一个指定的“种子点”开始，将其周围相邻的、且满足特定条件的区域,全部替换成新的颜色或值。

（图片来源网络，侵删）

想象一下，你有一个图像编辑器（比如Windows画图），你选择“油漆桶”工具，点击画布上的一块区域，这个区域就会瞬间被填充成你选择的颜色，Flood Fill就是实现这个“油漆桶”功能的核心算法。

应用场景：

图像编辑软件中的油漆桶工具。
填充封闭的图形。
地图游戏（如《文明》）中,填充一块连续的大陆。
解决一些二维网格上的搜索问题，岛屿数量”问题。

算法核心思想

Flood Fill的核心思想是“蔓延”，从一个起点开始，检查它的上下左右四个（或八个）邻居，如果邻居满足填充条件（颜色与原始起点相同），那么就对这个邻居进行同样的操作，这个过程不断重复,直到所有满足条件的相邻区域都被访问和填充。

这个过程天然具有递归的结构，或者可以用数据结构（栈或队列）来模拟递归的过程。

（图片来源网络，侵删）

C语言实现

我们将实现一个函数 floodFill,它接受以下参数：

image: 一个二维数组,代表图像的像素矩阵。
sr: 种子点的行坐标。
sc: 种子点的列坐标。
newColor: 要填充的新颜色。
rows: 图像的总行数。
cols: 图像的总列数。

函数的返回值是填充后的图像（在C语言中，我们通常直接在原数组上修改，所以返回 image 本身）。

递归法

这是最直观、最容易理解的方法，但它的缺点是，如果填充区域非常大，可能会导致栈溢出。

代码实现：

（图片来源网络，侵删）

#include <stdio.h>
#include <stdlib.h>
// 定义一个辅助函数，用于检查坐标是否在图像范围内
int isInside(int rows, int cols, int r, int c) {
    return (r >= 0 && r < rows && c >= 0 && c < cols);
}
// 递归的Flood Fill函数
void floodFillRecursive(int** image, int sr, int sc, int newColor, int rows, int cols, int originalColor) {
    // 1. 基本情况：如果当前坐标超出边界，或者颜色不是原始颜色，则返回
    if (!isInside(rows, cols, sr, sc) || image[sr][sc] != originalColor) {
        return;
    }
    // 2. 操作：将当前点的颜色更新为新颜色
    image[sr][sc] = newColor;
    // 3. 递归调用：对四个方向（上、下、左、右）进行填充
    floodFillRecursive(image, sr - 1, sc, newColor, rows, cols, originalColor); // 上
    floodFillRecursive(image, sr + 1, sc, newColor, rows, cols, originalColor); // 下
    floodFillRecursive(image, sr, sc - 1, newColor, rows, cols, originalColor); // 左
    floodFillRecursive(image, sr, sc + 1, newColor, rows, cols, originalColor); // 右
}
// 封装函数，提供更友好的接口
int** floodFill(int** image, int sr, int sc, int newColor, int rows, int cols) {
    // 获取种子点的原始颜色
    int originalColor = image[sr][sc];
    // 如果新颜色和原始颜色相同，则无需操作，防止无限递归
    if (originalColor == newColor) {
        return image;
    }
    // 调用递归核心函数
    floodFillRecursive(image, sr, sc, newColor, rows, cols, originalColor);
    return image;
}
// 辅助函数：打印图像
void printImage(int** image, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%2d ", image[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
// 辅助函数：释放图像内存
void freeImage(int** image, int rows) {
    for (int i = 0; i < rows; i++) {
        free(image[i]);
    }
    free(image);
}
int main() {
    // 示例1：简单填充
    int rows1 = 3, cols1 = 3;
    int** image1 = (int**)malloc(rows1 * sizeof(int*));
    for (int i = 0; i < rows1; i++) {
        image1[i] = (int*)malloc(cols1 * sizeof(int));
        for (int j = 0; j < cols1; j++) {
            image1[i][j] = 1; // 初始颜色为1
        }
    }
    image1[1][1] = 0; // 设置一个中心点为0
    image1[0][0] = 0; // 设置一个角落点为0
    printf("原始图像1:\n");
    printImage(image1, rows1, cols1);
    // 从(1,1)开始，将所有0的区域填充为2
    floodFill(image1, 1, 1, 2, rows1, cols1);
    printf("从(1,1)填充后图像1:\n");
    printImage(image1, rows1, cols1);
    freeImage(image1, rows1);
    // 示例2：防止无限递归
    int rows2 = 2, cols2 = 2;
    int** image2 = (int**)malloc(rows2 * sizeof(int*));
    for (int i = 0; i < rows2; i++) {
        image2[i] = (int*)malloc(cols2 * sizeof(int));
        image2[i][j] = 1;
    }
    printf("原始图像2:\n");
    printImage(image2, rows2, cols2);
    // 尝试用相同的颜色填充，算法应能正确处理
    floodFill(image2, 0, 0, 1, rows2, cols2);
    printf("尝试用相同颜色填充后图像2:\n");
    printImage(image2, rows2, cols2);
    freeImage(image2, rows2);
    return 0;
}

非递归法（使用栈）

为了避免递归可能导致的栈溢出，我们可以使用栈来手动管理需要填充的像素点，这种方法也被称为“深度优先搜索”的迭代实现。

算法流程：

创建一个空栈。
将种子点 (sr, sc) 压入栈中。
当栈不为空时，循环执行： a. 弹出栈顶的一个像素点 (r, c)。 b. 如果该像素点在图像范围内且颜色为原始颜色，则将其颜色更新为新颜色。 c. 将其四个邻居（上、下、左、右）压入栈中。

代码实现：

#include <stdio.h>
#include <stdlib.h>
// 定义一个坐标结构体
typedef struct {
    int r;
    int c;
} Point;
// 定义一个栈结构体
typedef struct {
    Point* data;
    int top;
    int capacity;
} Stack;
// 栈的初始化
Stack* createStack(int capacity) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->data = (Point*)malloc(capacity * sizeof(Point));
    s->top = -1;
    s->capacity = capacity;
    return s;
}
// 栈的销毁
void destroyStack(Stack* s) {
    free(s->data);
    free(s);
}
// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}
// 入栈
void push(Stack* s, Point p) {
    if (s->top == s->capacity - 1) {
        // 栈满，可以在这里实现扩容逻辑，为简单起见，我们假设容量足够
        printf("Stack is full!\n");
        return;
    }
    s->data[++(s->top)] = p;
}
// 出栈
Point pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        // 返回一个无效点，调用者应检查isEmpty
        Point invalid = {-1, -1};
        return invalid;
    }
    return s->data[(s->top)--];
}
// 非递归的Flood Fill函数 (使用栈)
int** floodFillStack(int** image, int sr, int sc, int newColor, int rows, int cols) {
    int originalColor = image[sr][sc];
    if (originalColor == newColor) {
        return image;
    }
    // 创建一个栈，容量设为图像大小，确保足够
    Stack* s = createStack(rows * cols);
    Point seed = {sr, sc};
    push(s, seed);
    while (!isEmpty(s)) {
        Point current = pop(s);
        int r = current.r;
        int c = current.c;
        // 检查当前点是否有效
        if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != originalColor) {
            continue;
        }
        // 填充当前点
        image[r][c] = newColor;
        // 将邻居压入栈
        push(s, (Point){r - 1, c}); // 上
        push(s, (Point){r + 1, c}); // 下
        push(s, (Point){r, c - 1}); // 左
        push(s, (Point){r, c + 1}); // 右
    }
    destroyStack(s);
    return image;
}

非递归法（使用队列）

使用队列可以实现“广度优先搜索”（BFS）版本的Flood Fill，与使用栈的DFS版本相比，BFS版本会逐层向外填充,而不是像DFS那样沿着一条路径一直走到底。

算法流程：

创建一个空队列。
将种子点 (sr, sc) 加入队列。
当队列不为空时，循环执行： a. 从队首取出一个像素点 (r, c)。 b. 如果该像素点在图像范围内且颜色为原始颜色，则将其颜色更新为新颜色。 c. 将其四个邻居（上、下、左、右）加入队尾。

代码实现 (使用数组模拟队列)：

#include <stdio.h>
#include <stdlib.h>
// 定义一个坐标结构体
typedef struct {
    int r;
    int c;
} Point;
// 定义一个队列结构体
typedef struct {
    Point* data;
    int front;
    int rear;
    int capacity;
} Queue;
// 队列的初始化
Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (Point*)malloc(capacity * sizeof(Point));
    q->front = 0;
    q->rear = -1;
    q->capacity = capacity;
    return q;
}
// 队列的销毁
void destroyQueue(Queue* q) {
    free(q->data);
    free(q);
}
// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->rear < q->front;
}
// 入队
void enqueue(Queue* q, Point p) {
    if (q->rear == q->capacity - 1) {
        // 队满，同样可以扩容
        printf("Queue is full!\n");
        return;
    }
    q->data[++(q->rear)] = p;
}
// 出队
Point dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        Point invalid = {-1, -1};
        return invalid;
    }
    return q->data[(q->front)++];
}
// 非递归的Flood Fill函数 (使用队列)
int** floodFillQueue(int** image, int sr, int sc, int newColor, int rows, int cols) {
    int originalColor = image[sr][sc];
    if (originalColor == newColor) {
        return image;
    }
    // 创建一个队列
    Queue* q = createQueue(rows * cols);
    Point seed = {sr, sc};
    enqueue(q, seed);
    while (!isEmpty(q)) {
        Point current = dequeue(q);
        int r = current.r;
        int c = current.c;
        if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != originalColor) {
            continue;
        }
        image[r][c] = newColor;
        enqueue(q, (Point){r - 1, c}); // 上
        enqueue(q, (Point){r + 1, c}); // 下
        enqueue(q, (Point){r, c - 1}); // 左
        enqueue(q, (Point){r, c + 1}); // 右
    }
    destroyQueue(q);
    return image;
}

总结与对比

方法	优点	缺点	适用场景
递归法	代码简洁，逻辑清晰，易于实现。	对于大面积填充，容易导致栈溢出。	填充区域不大，或对代码简洁性要求高的场景。
非递归（栈）	避免了栈溢出，是DFS的迭代实现。	需要手动管理栈，代码稍复杂。	填充区域可能很大，需要避免递归深度限制。
非递归（队列）	避免了栈溢出，是BFS的迭代实现，填充过程是逐层展开的。	需要手动管理队列，代码稍复杂。	当需要逐层填充或关心填充的“波纹”效应时。

在实际应用中，如果填充区域不大，递归法是首选，因为它最简单，如果处理的是可能非常大的图像（在游戏或专业软件中），那么使用栈或队列的非递归方法更为稳妥和安全，对于“油漆桶”工具这类应用，BFS（队列）和DFS（栈）在视觉上几乎没有区别。

C语言如何实现Floodfill算法？

什么是Flood Fill算法？

算法核心思想

C语言实现

递归法

非递归法（使用栈）

非递归法（使用队列）

总结与对比

相关文章

目录[+]