BFS（廣度優(yōu)先搜索）解決 Flood Fill 算法的基本思想是通過從起始點開始，逐層向外擴展，訪問所有與起始點相連且具有相同特性（顏色等）的區(qū)域。在 Flood Fill 中，通常是通過修改圖像的像素顏色。
下面是 BFS 解決 Flood Fill 算法的步驟：
- 初始化： 將起始點的顏色修改為新的顏色，將起始點加入隊列。
- BFS 遍歷： 使用隊列進行 BFS 遍歷。每次從隊列中取出一個位置，檢查其相鄰的位置是否符合條件（與起始點顏色相同），如果符合，則修改顏色并將其加入隊列。這樣，不斷擴展遍歷。
- 遍歷直到完成： 重復上述步驟，直到隊列為空，即沒有可繼續(xù)擴展的位置為止。此時，所有與起始點相連的區(qū)域都被成功修改。
在 Flood Fill 中，BFS 保證了相鄰區(qū)域的逐層遍歷，確保了所有相連的、顏色相同的區(qū)域都被填充為新的顏色。
01.圖像渲染
題目鏈接：https://leetcode.cn/problems/flood-fill/
有一幅以 m x n 的二維整數(shù)數(shù)組表示的圖畫 image ，其中 image[i][j] 表示該圖畫的像素值大小。
你也被給予三個整數(shù) sr , sc 和 newColor 。你應該從像素 image[sr][sc] 開始對圖像進行 上色填充 。
為了完成 上色工作 ，從初始像素開始，記錄初始坐標的 上下左右四個方向上 像素值與初始坐標相同的相連像素點，接著再記錄這四個方向上符合條件的像素點與他們對應 四個方向上 像素值與初始坐標相同的相連像素點，……，重復該過程。將所有有記錄的像素點的顏色值改為 newColor 。
最后返回 經(jīng)過上色渲染后的圖像 。
示例 1:
輸入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
輸出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在圖像的正中間，(坐標(sr,sc)=(1,1)),在路徑上所有符合條件的像素點的顏色都被更改成2。
注意，右下角的像素沒有更改為2，因為它不是在上下左右四個方向上與初始點相連的像素點。
示例 2:
輸入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
輸出: [[2,2,2],[2,2,2]]
思路
這個題我們可以使用最樸素的bfs遍歷來解決。
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-830434.html
class Solution {
const int dx[4] = {0, 0, 1, -1}; // 表示上、下、左、右四個方向的相對坐標變化
const int dy[4] = {-1, 1, 0, 0};
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int prev = image[sr][sc]; // 記錄起始位置的顏色
if (prev == color) return image; // 如果新舊顏色相同，不需要進行填充
int m = image.size(), n = image[0].size();
queue<pair<int, int>> q;
q.push({sr, sc});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
image[a][b] = color; // 修改當前位置的顏色
for (int i = 0; i < 4; ++i) {
int x = a + dx[i], y = b + dy[i];
// 判斷新的坐標是否越界，并且顏色與舊顏色相同
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
q.push({x, y});
}
}
}
return image;
}
};
-
初始化： 記錄起始位置的顏色
prev，如果起始顏色和目標顏色相同，直接返回原圖。 -
BFS 遍歷： 使用隊列
q進行 BFS 遍歷。從起始位置開始，逐層遍歷相鄰位置，將顏色修改為目標顏色。 - 遍歷直到完成： 重復上述步驟，直到隊列為空，即沒有可繼續(xù)擴展的位置為止。此時，所有與起始點相連的區(qū)域都被成功修改為新的顏色。
02.島嶼數(shù)量
題目鏈接：https://leetcode.cn/problems/number-of-islands/
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設該網(wǎng)格的四條邊均被水包圍。
示例 1：
輸入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
輸出：1
示例 2：
輸入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
輸出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300-
grid[i][j]的值為'0'或'1'
思路
使用bfs思想遍歷每一個方格，將一塊遍歷過的島嶼全都標記為海洋也就是0，或者使用同等大小的數(shù)組進行遍歷的標記。
代碼
class Solution {
const int dx[4] = {0, 0, 1, -1}; // 表示上、下、左、右四個方向的相對坐標變化
const int dy[4] = {1, -1, 0, 0};
int m, n; // m表示行數(shù)，n表示列數(shù)
queue<pair<int, int>> q; // 用于BFS的隊列
// BFS函數(shù)，從起點 (i, j) 開始遍歷并標記屬于同一島嶼的所有位置
void bfs(vector<vector<char>>& grid, int i, int j) {
q.push({i, j}); // 將起點入隊
grid[i][j] = '0'; // 標記已經(jīng)遍歷過的位置
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = a + dx[k], y = b + dy[k];
// 判斷新的坐標是否越界，并且是島嶼的一部分
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
q.push({x, y}); // 將相鄰的島嶼位置入隊
grid[x][y] = '0'; // 標記已經(jīng)遍歷過的位置
}
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size(); // 獲取行數(shù)
n = grid[0].size(); // 獲取列數(shù)
int ret = 0; // 記錄島嶼數(shù)量
// 遍歷整個網(wǎng)格
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
ret++; // 發(fā)現(xiàn)新的島嶼，增加計數(shù)
bfs(grid, i, j); // 使用BFS遍歷并標記所有屬于同一島嶼的位置
}
}
}
return ret; // 返回島嶼數(shù)量
}
};
-
初始化： 定義了方向數(shù)組
dx和dy，表示上、下、左、右四個方向的相對坐標變化。初始化隊列q，用于BFS遍歷。 -
BFS遍歷： 對于每個未被訪問的島嶼起點，調(diào)用
bfs函數(shù)進行BFS遍歷。在BFS過程中，將屬于同一島嶼的位置標記為已訪問。 -
遍歷整個網(wǎng)格： 使用兩層循環(huán)遍歷整個網(wǎng)格，如果發(fā)現(xiàn)未訪問過的島嶼起點，就調(diào)用
bfs函數(shù)進行遍歷，并增加島嶼數(shù)量計數(shù)。 - 返回結(jié)果： 最終返回島嶼的數(shù)量。
03.島嶼的最大面積
給你一個大小為 m x n 的二進制矩陣 grid 。
島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數(shù)目。
計算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
示例 1：
輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
輸出：6
解釋：答案不應該是 11 ，因為島嶼只能包含水平或垂直這四個方向上的 1 。
示例 2：
輸入：grid = [[0,0,0,0,0,0,0,0]]
輸出：0
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 50-
grid[i][j]為0或1
思路
總體和上面的題目解法一樣，只不過我們在遍歷每個島嶼時，順便計算個數(shù)即島嶼的面積，每次計算完再比較，最后返回最大的島嶼面積。
代碼
class Solution {
const int dx[4] = {0, 0, 1, -1}; // 上、下、右、左四個方向的相對坐標變化
const int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> q; // 用于BFS的隊列
int m, n; // m 表示行數(shù)，n 表示列數(shù)
// BFS 函數(shù)，從起點 (i, j) 開始遍歷并標記屬于同一島嶼的所有位置
int bfs(vector<vector<int>>& grid, int i, int j) {
int count = 1; // 記錄島嶼的大小
q.push({i, j}); // 將起點入隊
grid[i][j] = 0; // 標記已經(jīng)遍歷過的位置
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = a + dx[k], y = b + dy[k];
// 判斷新的坐標是否越界，并且是島嶼的一部分
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 0; // 標記已經(jīng)遍歷過的位置
count++; // 增加島嶼的大小
q.push({x, y}); // 將相鄰的島嶼位置入隊
}
}
}
return count;
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ret = 0; // 記錄最大島嶼面積
m = grid.size(); // 獲取行數(shù)
n = grid[0].size(); // 獲取列數(shù)
// 遍歷整個網(wǎng)格
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
ret = max(ret, bfs(grid, i, j)); // 計算并更新最大島嶼面積
}
}
}
return ret; // 返回最大島嶼面積
}
};
-
初始化： 定義了方向數(shù)組
dx和dy，表示上、下、左、右四個方向的相對坐標變化。初始化隊列q，用于BFS遍歷。 -
BFS遍歷： 對于每個未被訪問的島嶼起點，調(diào)用
bfs函數(shù)進行BFS遍歷。在BFS過程中，將屬于同一島嶼的位置標記為已訪問，并統(tǒng)計島嶼的大小。 -
遍歷整個網(wǎng)格： 使用兩層循環(huán)遍歷整個網(wǎng)格，如果發(fā)現(xiàn)未訪問過的島嶼起點，就調(diào)用
bfs函數(shù)進行遍歷，并計算并更新最大島嶼面積。 - 返回結(jié)果： 最終返回最大島嶼面積。
04.被圍繞的區(qū)域
題目鏈接：https://leetcode.cn/problems/surrounded-regions/
給你一個 m x n 的矩陣 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。
示例 1：
輸入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
輸出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解釋：被圍繞的區(qū)間不會存在于邊界上，換句話說，任何邊界上的 'O' 都不會被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會被填充為 'X'。如果兩個元素在水平或垂直方向相鄰，則稱它們是“相連”的。
示例 2：
輸入：board = [["X"]]
輸出：[["X"]]
提示：
m == board.lengthn == board[i].length1 <= m, n <= 200-
board[i][j]為'X'或'O'
思路
這里我們可以使用bfs先處理所有與邊界有關的位置，把它修改成其他字符，再依次遍歷，留在格子中的字母O就是需要被修改的，而改成其他字符的就可以改回字母O。文章來源：http://www.zghlxwxcb.cn/news/detail-830434.html
代碼
class Solution {
const int dx[4] = {0, 0, 1, -1}; // 上、下、右、左四個方向的相對坐標變化
const int dy[4] = {-1, 1, 0, 0};
int m, n; // m 表示行數(shù)，n 表示列數(shù)
queue<pair<int, int>> q; // 用于BFS的隊列
// BFS 函數(shù)，從起點 (i, j) 開始遍歷并標記屬于同一區(qū)域的所有位置
void bfs(vector<vector<char>>& board, int i, int j) {
q.push({i, j}); // 將起點入隊
board[i][j] = '#'; // 標記已經(jīng)遍歷過的位置
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = a + dx[k], y = b + dy[k];
// 判斷新的坐標是否越界，并且是未被圍繞的區(qū)域
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
board[x][y] = '#'; // 標記已經(jīng)遍歷過的位置
q.push({x, y}); // 將相鄰的未被圍繞的區(qū)域位置入隊
}
}
}
}
public:
void solve(vector<vector<char>>& board) {
m = board.size(); // 獲取行數(shù)
n = board[0].size(); // 獲取列數(shù)
// 對邊界上的'O'進行BFS遍歷，標記為'#'
for (int i = 0; i < n; ++i) {
if (board[0][i] == 'O') bfs(board, 0, i);
if (board[m - 1][i] == 'O') bfs(board, m - 1, i);
}
for (int i = 1; i < m - 1; ++i) {
if (board[i][0] == 'O') bfs(board, i, 0);
if (board[i][n - 1] == 'O') bfs(board, i, n - 1);
}
// 遍歷整個網(wǎng)格，將未被標記的'O'修改為'X'，已經(jīng)標記的'#'修改回'O'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '#') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}
}
};
到了這里，關于算法沉淀——BFS 解決 FloodFill 算法（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
