详细讲解泛洪算法

泛洪算法（Flood Fill Algorithm）是一种图遍历算法，用于填充图中的区域。它从一个起始点开始，沿着图的连接路径，访问并标记所有与起始点相连的区域。主要用途包括图像处理、图形填充、游戏开发中的地图填充等。

以下是泛洪算法的详细讲解：

1. 算法思想：

• 选择一个起始点作为初始种子点。

• 将该种子点标记为已访问。

• 将种子点入队列（或栈，具体实现中可以使用队列、栈或其他数据结构）。

• 不断从队列中取出节点，探索与当前节点相邻且未访问的节点，并标记为已访问。

• 将这些相邻未访问的节点加入队列，继续循环直到队列为空。

2. 基本步骤：

• 初始化：选择起始点，将其标记为已访问，加入队列。

• 循环：从队列中取出一个节点，标记其相邻未访问的节点，并将它们加入队列。

• 直到队列为空，算法结束。

3. 实现细节：

• 队列管理：使用队列数据结构，确保按照广度优先的方式遍历节点。

• 标记节点：在访问过的节点上打上标记，防止重复访问。

• 方向探索：通常需要考虑上、下、左、右等方向，具体根据问题需求而定。

4. 应用场景：

• 图像处理：用于填充图像中的封闭区域，比如油漆桶工具。

• 游戏开发：地图填充、区域连接等。

• 图形学：生成连通区域。

5. 
   

泛洪算法的关键点是通过队列来管理待访问的节点，确保按照广度优先的方式遍历整个区域。这种算法的时间复杂度与图中节点数量成正比。

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

using namespace std;

// 定义图的大小
const int ROWS = 5;
const int COLS = 5;

// 定义四个方向的移动
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

// 泛洪算法函数
void floodFill(vector<vector<char>>& grid, int startX, int startY) {
    // 使用队列来管理待访问的节点
    queue<pair<int, int>> q;
    q.push({startX, startY});

    // 标记起始点为已访问
    grid[startX][startY] = 'X';

    while (!q.empty()) {
        // 获取当前节点的坐标
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 检查新坐标是否在图的范围内且未访问
            if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS && grid[nx][ny] == 'O') {
                // 标记节点为已访问
                grid[nx][ny] = 'X';
                // 将新节点加入队列，以便后续遍历
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    // 示例图的初始化
    vector<vector<char>> grid = {
        {'O', 'O', 'O', 'O', 'X'},
        {'O', 'O', 'X', 'O', 'X'},
        {'X', 'X', 'X', 'O', 'O'},
        {'O', 'X', 'O', 'O', 'O'},
        {'X', 'X', 'O', 'X', 'X'}
    };

    // 起始点坐标
    int startX = 0;
    int startY = 0;

    // 调用泛洪算法
    floodFill(grid, startX, startY);

    // 打印结果
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            cout << grid[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}