目錄

1. 概述

2. BFS 的基本原理

3. Flood Fill 算法

4. BFS 實現(xiàn) Flood Fill 的步驟

5. C++ 實現(xiàn)

6. 代碼解析

7. 復(fù)雜度分析

8. 應(yīng)用場景

總結(jié)

---

1. 概述

????????Flood Fill 算法是一種用于填充封閉區(qū)域的算法，常用于圖像處理、繪圖工具和游戲開發(fā)中。BFS（廣度優(yōu)先搜索）是解決 Flood Fill 問題的一種有效方法，特別適用于矩陣或網(wǎng)格中的區(qū)域填充。

2. BFS 的基本原理

????????BFS 是一種圖遍歷算法，從起始點開始，逐層向外擴(kuò)展，直到遍歷完所有可達(dá)節(jié)點。BFS 使用隊列來存儲待訪問的節(jié)點，確保按照層級順序訪問。

3. Flood Fill 算法

????????Flood Fill 算法的目標(biāo)是從一個起始點開始，填充所有與之相連且滿足特定條件的區(qū)域。常見的應(yīng)用包括圖像中的顏色填充、迷宮求解等。

4. BFS 實現(xiàn) Flood Fill 的步驟

1. 初始化：選擇一個起始點，并將其顏色更改為目標(biāo)顏色。

2. 隊列操作：將起始點加入隊列。

3. 遍歷：從隊列中取出一個點，檢查其相鄰的點（上下左右），如果相鄰點滿足條件（如顏色相同），則將其顏色更改為目標(biāo)顏色，并將其加入隊列。

4. 重復(fù)：重復(fù)步驟3，直到隊列為空。

5. C++ 實現(xiàn)

以下是一個使用 BFS 實現(xiàn) Flood Fill 的 C++ 代碼示例：

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 定義方向數(shù)組，表示上下左右四個方向
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;
}

6. 代碼解析

• 方向數(shù)組：dx?和?dy?數(shù)組用于表示上下左右四個方向的移動。

• 隊列：使用?queue<pair<int, int>>?來存儲待處理的像素點。

• 邊界檢查：在遍歷相鄰點時，檢查是否越界。

• 顏色更新：如果相鄰點的顏色與起始點顏色相同，則更新其顏色并加入隊列。

7. 復(fù)雜度分析

• 時間復(fù)雜度：O(M*N)，其中 M 和 N 分別是圖像的行數(shù)和列數(shù)。每個像素最多被訪問一次。

• 空間復(fù)雜度：O(M*N)，最壞情況下隊列中可能存儲所有像素點。

8. 應(yīng)用場景

• 圖像處理：填充圖像中的封閉區(qū)域。

• 游戲開發(fā)：地圖填充、迷宮求解等。

• 計算機(jī)圖形學(xué)：區(qū)域選擇、顏色填充等。

總結(jié)

????????BFS 是一種高效且易于實現(xiàn)的算法，適用于 Flood Fill 問題。通過逐層擴(kuò)展，BFS 能夠確保所有符合條件的區(qū)域都被填充。在實際應(yīng)用中，BFS 的隊列實現(xiàn)和邊界檢查是關(guān)鍵點，確保算法的正確性和效率。