详细讲解泛洪算法

泛洪算法（Flood Fill Algorithm）是一种在计算机图形学和图像处理中常用的填充算法。它的主要目标是在一个二维的网格或位图上，根据给定的起始点和填充颜色，将特定区域内的像素点替换为目标颜色。

泛洪算法从起始点开始，将其填充颜色与目标颜色比较，如果相同，则将该点的颜色替换为目标颜色，并将其相邻的未填充点加入待处理的点集中。然后继续对待处理点集中的点进行相同的操作，直到待处理点集为空。

泛洪算法的关键在于通过递归或队列等数据结构来存储待处理的点集，从而实现对整个区域的遍历。算法需要注意避免重复处理已经填充的点，否则可能导致无限循环。

泛洪算法通常用于图像编辑软件中的填充工具，用户可以选择一个起始点和填充颜色，然后算法会自动将相邻的相同颜色的区域进行填充。它也可以用于计算机游戏中的地图区域标记、图像分割等应用场景。

需要注意的是，泛洪算法对于复杂的图形或边界不规则的区域可能会存在一些限制和缺陷，例如可能会出现漏填或过填的情况。在实际应用中，可能需要结合其他算法或技术来处理这些问题。

简单泛洪算法示例：

#include <iostream>
#include <vector>
#include <queue>

// 定义二维坐标结构体
struct Point {
    int x;
    int y;
};

// 泛洪算法函数
void floodFill(std::vector<std::vector<int> >& image, int startX, int startY, int newColor) {
    int rows = image.size();
    int cols = image[0].size();
    int oldColor = image[startX][startY];
    
    // 判断起始点是否在图像范围内
    if (startX < 0 || startX >= rows || startY < 0 || startY >= cols || oldColor == newColor) {
        return;
    }
    
    std::queue<Point> q;
    q.push(Point{startX, startY});
    
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        
        int x = p.x;
        int y = p.y;
        
        // 将当前点的颜色替换为目标颜色
        image[x][y] = newColor;
        
        // 检查上下左右四个相邻点
        if (x - 1 >= 0 && image[x - 1][y] == oldColor) {
            q.push(Point{x - 1, y});
        }
        if (x + 1 < rows && image[x + 1][y] == oldColor) {
            q.push(Point{x + 1, y});
        }
        if (y - 1 >= 0 && image[x][y - 1] == oldColor) {
            q.push(Point{x, y - 1});
        }
        if (y + 1 < cols && image[x][y + 1] == oldColor) {
            q.push(Point{x, y + 1});
        }
    }
}

// 打印图像
void printImage(const std::vector<std::vector<int> >& image) {
    int rows = image.size();
    int cols = image[0].size();
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << image[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    // 定义一个5x5的图像
    std::vector<std::vector<int> > image(5, std::vector<int>(5, 0));
    
    // 在图像中设置一些初始颜色
    image[1][1] = 1;
    image[1][2] = 1;
    image[2][2] = 1;
    image[3][3] = 1;
    
    std::cout << "初始图像：" << std::endl;
    printImage(image);
    
    // 对起始点 (2, 2) 使用泛洪算法填充新颜色为 2
    floodFill(image, 2, 2, 2);
    
    std::cout << "填充后的图像：" << std::endl;
    printImage(image);
    
    return 0;
}

上述代码使用一个二维数组表示图像，0表示空白，1表示原始颜色。使用泛洪算法将起始点(2, 2)周围的相同颜色区域替换为新的颜色2。程序输出初始图像和填充后的图像。注意，此示例使用C++98语法，并使用C++标准库中的vector和queue容器。

如果你不想使用<vector>和<queue>头文件，可以使用C-style数组和自定义的队列数据结构来代替。以下是一个修改后的示例代码：

#include <iostream>

// 定义二维坐标结构体
struct Point {
    int x;
    int y;
};

// 自定义队列数据结构
class Queue {
private:
    static const int MAX_SIZE = 1000;
    Point data[MAX_SIZE];
    int front;
    int rear;
public:
    Queue() : front(-1), rear(-1) {}
    
    bool isEmpty() {
        return front == -1 && rear == -1;
    }
    
    bool isFull() {
        return (rear + 1) % MAX_SIZE == front;
    }
    
    void enqueue(Point p) {
        if (isFull()) {
            std::cout << "Queue is full." << std::endl;
            return;
        }
        
        if (isEmpty()) {
            front = 0;
        }
        
        rear = (rear + 1) % MAX_SIZE;
        data[rear] = p;
        std::cout<<"入队点："<<"("<<p.x<<" ,"<<p.y<<")"<<";";
    }
    
    Point dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty." << std::endl;
            return Point{-1, -1};
        }
        
        Point p = data[front];
        
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % MAX_SIZE;
        }
        
        return p;
    }
};

// 泛洪算法函数
void floodFill(int image[][5], int rows, int cols, int startX, int startY, int newColor) {
    int oldColor = image[startX][startY];
    
    // 判断起始点是否在图像范围内
    if (startX < 0 || startX >= rows || startY < 0 || startY >= cols || oldColor == newColor) {
        return;
    }
    
    Queue q;
    q.enqueue(Point{startX, startY});
    
    while (!q.isEmpty()) {
        Point p = q.dequeue();
        
        int x = p.x;
        int y = p.y;
        
        // 将当前点的颜色替换为目标颜色
        image[x][y] = newColor;
        
        // 检查上下左右四个相邻点
        if (x - 1 >= 0 && image[x - 1][y] == oldColor) {
            q.enqueue(Point{x - 1, y});
        }
        if (x + 1 < rows && image[x + 1][y] == oldColor) {
            q.enqueue(Point{x + 1, y});
        }
        if (y - 1 >= 0 && image[x][y - 1] == oldColor) {
            q.enqueue(Point{x, y - 1});
        }
        if (y + 1 < cols && image[x][y + 1] == oldColor) {
            q.enqueue(Point{x, y + 1});
        }
    }
}

// 打印图像
void printImage(int image[][5], int rows, int cols) {
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            std::cout << image[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    // 定义一个5x5的图像
    int image[5][5] = { {0, 0, 0, 0, 0},
                        {0, 1, 1, 0, 0},
                        {0, 0, 1, 0, 0},
                        {0, 0, 0, 1, 0},
                        {0, 0, 0, 0, 0} };
    
    int rows = 5;
    int cols = 5;
    
    std::cout << "初始图像：" << std::endl;
    printImage(image, rows, cols);
    
    // 对起始点 (2, 2) 使用泛洪算法填充新颜色为 2
    floodFill(image, rows, cols, 2, 2, 2);
    
    std::cout << "填充后的图像：" << std::endl;
    printImage(image, rows, cols);
    
    return 0;
}

在这个修改后的代码中，使用了一个Queue类来代替标准库中的队列。Queue类使用循环数组实现队列的基本操作，并与泛洪算法函数一起使用。注意，数组大小被限制为MAX_SIZE，在此示例中设置为1000。