floodfill算法（6题）

本质就是找出性质相似的连通块

目录

1.图像渲染

2.岛屿数量

 3.岛屿的最大面积

4.被围绕的区域

 5.太平洋大西洋水流问题

6.扫雷游戏

---

1.图像渲染

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

我们使用深度优先遍历去遍历即可，也不需要返回值。

值得注意的有两点

1.如果起始位置的颜色和目标颜色相同，直接返回即可。

2.由于我们遍历是向上下左右遍历，因此我们进入dfs函数之前需要把初始位置颜色给改了

class Solution {
public:int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int m, n;int initcolor;int aimcolor;vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {m = image.size();n = image[0].size();initcolor = image[sr][sc];aimcolor = color;if(image[sr][sc] != color){image[sr][sc] = color;dfs(image, sr, sc);}return image;}void dfs(vector<vector<int>>& image, int x,int y){for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && image[i][j] == initcolor){image[i][j] = aimcolor;dfs(image,i,j);}}}
};

2.岛屿数量

200. 岛屿数量 - 力扣（LeetCode）

        算法思路都是一样的。这里我们找到一块陆地就让ret++。然后再把相连的所有陆地都标记起来，这样子下次找岛屿时就不会找到相同的地块了。并不需要恢复路径。

class Solution {
public:int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int m, n;int check[310][310];int ret = 0;int numIslands(vector<vector<char>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1' && check[i][j] == false){check[i][j] = true;dfs(grid, i, j);ret++;}}}return ret;}void dfs(vector<vector<char>>& grid, int x, int y){for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && grid[i][j] == '1' && check[i][j] == false){check[i][j] = true;dfs(grid,i,j);}}}
};

 3.岛屿的最大面积

LCR 105. 岛屿的最大面积 - 力扣（LeetCode）

        这题代码和岛屿数量几乎一样。我们要记录岛屿的面积只需要定义一个全局的count变量，每次dfs进入一块新的地之后把count++即可。每次找到一块新的未遍历的地的时候先将count清零

class Solution {
public:int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int m, n;int check[55][55];int ret = 0;int count;int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1 && check[i][j] == false){count = 0;check[i][j] = true;dfs(grid, i, j);ret = max(ret, count);}}}return ret;}void dfs(vector<vector<int>>& grid, int x, int y){count++;for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && grid[i][j] == 1 && check[i][j] == false){check[i][j] = true;dfs(grid,i,j);}}}};

4.被围绕的区域

130. 被围绕的区域 - 力扣（LeetCode）

    题目的意思是把四周都围上‘X’的'O'变成‘X’。于是给我们的图中有两种情况需要分别讨论。

    这样会非常麻烦。因此我们正难则反，遍历一遍四周，遇到‘O’时进行一次深度优先遍历就能找出所有与边缘相连的‘O’。我们先把这些O改成‘.’。

        对四周进行遍历后我们再把‘.’重新还原变成‘O’，把原来没有被改变的‘O’改成‘X’。

class Solution {
public:int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int m, n;void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();for(int i = 0; i < n; i++){if(board[0][i] == 'O')dfs(board, 0, i);if(board[m-1][i] == 'O')dfs(board, m - 1, i);}for(int i = 0; i < m; i++){if(board[i][0] == 'O')dfs(board, i, 0);if(board[i][n - 1] == 'O' )dfs(board, i, n - 1);}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O'){board[i][j] = 'X';}else if(board[i][j] == '.'){board[i][j] = 'O';}}}}void dfs(vector<vector<char>>& board, int x, int y){board[x][y] = '.';for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && board[i][j] == 'O' ){board[i][j] = '.';dfs(board,i,j);}}}};

 5.太平洋大西洋水流问题

 417. 太平洋大西洋水流问题 - 力扣（LeetCode）

         依然也是正难则反的思路。我们从头到位遍历一次数组，每到一个位置就进行一次深度优先遍历的话复杂度太高。因此我们选择逆向，从靠近海边的位置进行逆向查找。这样每个格子被标记到之后只会被查到一次。

        这里我们开两个数组分别标记能流到大西洋和太平洋的位置。为了辨识数组这里选择传了一个标记数字。

class Solution {
public:int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int m, n;int check1[210][210];int check2[210][210];vector<vector<int>> ret;vector<vector<int>> pacificAtlantic(vector<vector<int>>& board) {m = board.size();n = board[0].size();for(int i = 0; i < n; i++){check1[0][i] = 1;dfs(board, 0, i,1);}for(int j = 0; j < m; j++){check1[j][0] = 1;dfs(board,j ,0,1);}for(int i = 0; i < n; i++){check2[m-1][i] = 1;dfs(board, m-1, i, 2);}for(int j = 0; j < m; j++){check2[j][n-1] = 1;dfs(board, j, n - 1,2);}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (check1[i][j] && check2[i][j]) {ret.push_back({i, j});}}}return ret;}void dfs(vector<vector<int>>& board, int x, int y, int z){for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && board[i][j] >= board[x][y]){if(z == 1 && check1[i][j] == false){check1[i][j] = true;dfs(board,i,j,1);}else if(z == 2 && check2[i][j] == false){check2[i][j] = true;dfs(board,i,j,2);}}}}
};

6.扫雷游戏

529. 扫雷游戏 - 力扣（LeetCode）

        这题需要注意的点不多。

        第一就是某点周围有雷和无雷后续的情况是不同的，第二就是遍历的时候注意已经走过的路不用再走，即board[i][j] == 'E'时我们才继续

class Solution {
public:int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};int m, n;vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {m = board.size();n = board[0].size();int x = click[0];int y = click[1];if(board[x][y] ==  'M'){board[x][y] = 'X';return board;}dfs(board, x, y);return board;}void dfs(vector<vector<char>>& board, int x, int y){int flag = 0;for(int k = 0; k < 8; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n ){if(board[i][j] == 'M'){flag++;}}}if(flag){board[x][y] = '0' + flag;return ;}else{board[x][y] = 'B';for(int k = 0; k < 8; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && board[i][j] == 'E'){dfs(board, i, j);}}}}
};