当前位置：首页 > news >正文

BFS与Flood Fill：算法原理、实现细节与复杂度分析

news 2025/8/14 7:21:13

1. 概述

2. BFS 的基本原理

3. Flood Fill 算法

4. BFS 实现 Flood Fill 的步骤

5. C++ 实现

6. 代码解析

7. 复杂度分析

8. 应用场景

总结

1. 概述

Flood Fill 算法是一种用于填充封闭区域的算法，常用于图像处理、绘图工具和游戏开发中。BFS（广度优先搜索）是解决 Flood Fill 问题的一种有效方法，特别适用于矩阵或网格中的区域填充。

2. BFS 的基本原理

BFS 是一种图遍历算法，从起始点开始，逐层向外扩展，直到遍历完所有可达节点。BFS 使用队列来存储待访问的节点，确保按照层级顺序访问。

3. Flood Fill 算法

Flood Fill 算法的目标是从一个起始点开始，填充所有与之相连且满足特定条件的区域。常见的应用包括图像中的颜色填充、迷宫求解等。

4. BFS 实现 Flood Fill 的步骤

初始化：选择一个起始点，并将其颜色更改为目标颜色。
队列操作：将起始点加入队列。
遍历：从队列中取出一个点，检查其相邻的点（上下左右），如果相邻点满足条件（如颜色相同），则将其颜色更改为目标颜色，并将其加入队列。
重复：重复步骤3，直到队列为空。

5. C++ 实现

以下是一个使用 BFS 实现 Flood Fill 的 C++ 代码示例：

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 定义方向数组，表示上下左右四个方向
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};void floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {int oldColor = image[sr][sc];if (oldColor == newColor) return; // 如果新旧颜色相同，直接返回int rows = image.size();int cols = image[0].size();queue<pair<int, int>> q;q.push({sr, sc});image[sr][sc] = newColor;while (!q.empty()) {auto current = q.front();q.pop();int x = current.first;int y = current.second;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 && image[nx][ny] == oldColor) {image[nx][ny] = newColor;q.push({nx, ny});}}}
}int main() {vector<vector<int>> image = {{1, 1, 1},{1, 1, 0},{1, 0, 1}};int sr = 1, sc = 1, newColor = 2;floodFill(image, sr, sc, newColor);for (const auto& row : image) {for (int pixel : row) {cout << pixel << " ";}cout << endl;}return 0;
}