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);
}
}
}
}
};