floodfill算法（6题）

目录

1.图像渲染

1.dfs

2.bfs

2.岛屿数量

1.dfs

2.bfs

3.岛屿的最大面积

1.dfs

2.bfs

4.被围绕的区域

1.dfs

2.bfs

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

6.扫雷游戏

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

1.图像渲染

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

1.dfs

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

值得注意的有两点

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.bfs

只是更换遍历方式，利用队列来进行层序遍历

class Solution { public: int dx[4] = {0 , 0, -1, 1}; int dy[4] = {1 , -1 ,0 , 0}; int m, n; typedef pair<int, int> pii; vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { m = image.size(); n = image[0].size(); int initcolor = image[sr][sc]; if(image[sr][sc] == color)return image; queue<pii> q; q.push({sr, sc}); while(q.size()) { auto[a, b] = q.front(); q.pop(); image[a][b] = color; for(int k = 0; k < 4; k++) { int i = a + dx[k]; int j = b + dy[k]; if(i >= 0 && i < m && j >=0 && j < n && image[i][j] == initcolor) { q.push({i,j}); } } } return image; } };

2.岛屿数量

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

1.dfs

算法思路都是一样的。这里我们找到一块陆地就让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); } } } };

2.bfs

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) { bfs(grid, i, j); ret++; } } } return ret; } void bfs(vector<vector<char>>& grid, int x, int y) { queue<pair<int, int> > q; q.push({x, y}); check[x][y] = true; while(q.size()) { auto[a, b] = q.front(); q.pop(); for(int k = 0; k < 4; k++) { int i = a + dx[k]; int j = b + dy[k]; if(i >= 0 && i < m && j >=0 && j < n && grid[i][j] == '1' && check[i][j] == false) { q.push({i , j}); check[i][j] = true; } } } } };

3.岛屿的最大面积

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

1.dfs

这题代码和岛屿数量几乎一样。我们要记录岛屿的面积只需要定义一个全局的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); } } } };

2.bfs

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; bfs(grid, i, j); ret = max(ret, count); } } } return ret; } void bfs(vector<vector<int>>& grid, int x, int y) { count++; check[x][y] = true; queue<pair<int, int>> q; q.push({x, y}); while(q.size()) { auto[a,b] = q.front(); q.pop(); for(int k = 0; k < 4; k++) { int i = a + dx[k]; int j = b + dy[k]; if(i >= 0 && i < m && j >=0 && j < n && grid[i][j] == 1 && check[i][j] == false) { check[i][j] = true; count++; q.push({i,j}); } } } } };

4.被围绕的区域

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

1.dfs

题目的意思是把四周都围上‘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); } } } };

2.bfs

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')bfs(board, 0, i); if(board[m-1][i] == 'O')bfs(board, m - 1, i); } for(int i = 0; i < m; i++) { if(board[i][0] == 'O')bfs(board, i, 0); if(board[i][n - 1] == 'O' )bfs(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 bfs(vector<vector<char>>& board, int x, int y) { board[x][y] = '.'; queue<pair<int, int>> q; q.push({x, y}); while(q.size()) { auto [a, b] = q.front(); q.pop(); for(int k = 0; k < 4; k++) { int i = a + dx[k]; int j = b + dy[k]; if(i >= 0 && i < m && j >=0 && j < n && board[i][j] == 'O' ) { board[i][j] = '.'; q.push({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); } } } } };