目錄

FloodFill問題

圖像渲染

島嶼數量

島嶼的最大面積

被圍繞的區域

---

FloodFill問題

FloodFill就是洪水灌溉的意思，假設有下面的一塊田地，負數代表是凹地，正數代表是凸地，數字的大小表示凹或者凸的程度。現在下一場大雨，請問大雨下完，這塊田地會有幾處積水

會發現會有3處積水，FloodFill問題的本質就是找到性質相同的連通塊。所以可以使用dfs或者bfs解決。使用兩種算法的原理是相同的，只是實現方法不同。

圖像渲染

733. 圖像渲染 - 力扣（LeetCode）

從給定的點開始寬搜，將周圍等于給定的點的顏色全都改成目標顏色即可

class Solution {
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int m = image.size(), n = image[0].size();vector<vector<int>> v(m, vector<int>(n, 0));queue<pair<int, int>> q;q.push({sr, sc});v[sr][sc] = 1;int flag = image[sr][sc];int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){int x = q.front().first, y = q.front().second;q.pop();image[x][y] = color;for(int i = 0;i < 4;i ++){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && image[a][b] == flag && v[a][b] == 0) {q.push({a, b});v[a][b] = 1;}}}return image;}
};

并且要注意數組全是0，且flag也是0的情況，所以添加一個標記數組。不讓一個元素重復放進隊列?

島嶼數量

200. 島嶼數量 - 力扣（LeetCode）

直接遍歷一下二維數組，當遇到1時，就使用bfs將這個島嶼全部變成0，然后繼續向后遍歷二維數組，等到遍歷完后，進行了幾次bfs就有幾個島嶼

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size(), ans = 0;for(int i = 0;i < m;i ++)for(int j = 0;j < n;j ++)if(grid[i][j] == '1'){ans ++;bfs(grid, i, j, m, n);}return ans;}void bfs(vector<vector<char>>& grid, int x, int y, int m, int n){queue<pair<int, int>> q;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};q.push({x, y});grid[x][y] = '0';while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == '1'){q.push({a, b});grid[a][b] = '0';}}}}
};

島嶼的最大面積

695. 島嶼的最大面積 - 力扣（LeetCode）

直接遍歷二維數組，當遇到1時，也就是遇到島嶼時，直接使用bfs將這個島嶼全部變成0，并在這期間計算出這個島嶼的面積，也就是每向隊列中放入一個數據就++，然后最后返回，與答案比較

class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size(), ans = 0;for(int i = 0;i < m;i ++)for(int j = 0;j < n;j ++)if(grid[i][j] == 1)ans = max(ans, dfs(grid, m, n, i, j));return ans;}int dfs(vector<vector<int>>& grid, int m, int n, int x, int y){queue<pair<int, int>> q;q.push({x, y});grid[x][y] = 0;int sum = 1;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1){q.push({a, b});grid[a][b] = 0;sum ++;}}}return sum;}
};

被圍繞的區域

130. 被圍繞的區域 - 力扣（LeetCode）

這道題的重點是邊緣的O是不算被X圍繞的，而我們要找的是一個O的連通塊，并且這個連通塊里面全部的O都要被X圍繞。所以，我們可以將與邊緣的O連通的塊排除，剩下的就都是被包圍的

class Solution {
public:void solve(vector<vector<char>>& board) {// 遍歷邊界，若邊界上的是O，則進行寬搜，將與這個O相連的所有O標記，被標記的O不會被變成Xint m = board.size(), n = board[0].size();vector<vector<int>> flag(m, vector<int>(n, 0));// 第一行for(int i = 0;i < n;i ++)if(board[0][i] == 'O')bfs(board, flag, m, n, 0, i);// 最后一行for(int i = 0;i < n;i ++)if(board[m - 1][i] == 'O')bfs(board, flag, m, n, m - 1, i);// 第一列for(int i = 1;i < m - 1;i ++)if(board[i][0] == 'O')bfs(board, flag, m, n, i, 0);// 最后一列for(int i = 1;i < m - 1;i ++)if(board[i][n - 1] == 'O')bfs(board, flag, m, n, i, n - 1);// 遍歷一遍數組，當字符是O，并且flag數組中是0，說明這個是被X包含的for(int i = 0;i < m;i ++)   for(int j = 0;j < n;j ++)if(board[i][j] == 'O' && flag[i][j] == 0) board[i][j] = 'X';}void bfs(vector<vector<char>>& board, vector<vector<int>>& flag, int m, int n, int x, int y){queue<pair<int, int>> q;q.push({x, y});flag[x][y] = 1;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && board[a][b] == 'O' && flag[a][b] == 0){q.push({a, b});flag[a][b] = 1;}}}}
};

要注意board數組全是O的情況，所以只有當標記數組為0才放進隊列當中。不讓一個元素重復放入隊列