我爱学算法之——floodfill算法（上）

前言

Flood Fill（也称为种子填充算法）是一种用于确定连接到多维数组中给定节点的区域的算法

核心思想

• 从起点开始：从一个初始像素（种子点）开始
• 扩散填充：向四周（通常为4方向或8方向）扩展
• 条件匹配：只填充与种子点颜色相同且相邻的像素
• 避免重复：标记已访问的位置，防止重复处理

一、图像渲染

题目解析

给定一个 m*n 的二维数组，从起始位置 [sr,sc] 开始，将从起始位置的 上下左右 四个方向上 相邻且与起始位置初始颜色相同的像素点进行染色，直到没有其他原始颜色的相邻像素。

算法思路

这道题整体还是非常简单的，从起始位置开始，进行一次深度优先遍历 DFS 即可。

注意：当起始位置[sr, sc]的颜色和目标颜色 color 相同时，直接返回原二维数组即可。

代码实现

classSolution{int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};public:voiddfs(vector<vector<int>>& image,int i,int j,int srcColor,int destColor){// 变色int m = image.size();int n = image[0].size(); image[i][j]= destColor;for(int k =0; k <4; k++){int x = i + dx[k];int y = j + dy[k];if(x >=0&& x < m && y >=0&& y < n && image[x][y]== srcColor)dfs(image, x, y, srcColor, destColor);}} vector<vector<int>>floodFill(vector<vector<int>>& image,int sr,int sc,int color){if(image[sr][sc]!= color)dfs(image, sr, sc, image[sr][sc], color);return image;}};

二、岛屿数量

题目解析

给定一个n*m的二维数组，其中1表示陆地、0表示海洋；

多个相邻的陆地可以看做是一座岛屿，要求计算网格中岛屿的数量

算法思路

遍历grid数组，遍历到陆地(1)并且该陆地没有和其他陆地形成岛屿（没有被BFS/DFS遍历过），就从该节点进行一次BFS/DFS遍历。

这样我们只需要统计在遍历grid时，进行BFS/DFS的次数即可。

这里使用 DFS 来接解决这道题

代码实现

classSolution{int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};bool vis[300][300];public:voiddfs(vector<vector<char>>& grid,int i,int j){ vis[i][j]=true;int m = grid.size(), n = grid[0].size();for(int k =0; k <4; k++){int x = i + dx[k];int y = j + dy[k];if(x >=0&& x < m && y >=0&& y < n &&!vis[x][y]&& grid[x][y]=='1')dfs(grid, x, y);}}intnumIslands(vector<vector<char>>& grid){int m = grid.size();int n = grid[0].size();int ret =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]=='1'&&!vis[i][j]){dfs(grid, i, j); ret++;}}}return ret;}};

三、岛屿的最大面积

题目解析

算法思路

这道题的结题思路也是和求岛屿数量大同小异；

还是遍历grid数组，在遍历到陆地并且该陆地没有和其他陆地组成岛屿。（遍历到1并且该位置没有被遍历过）

就从该位置进行一次BFS遍历（DFS也可以解决），并求出岛屿的面积；

然后统计岛屿面积的最大值 然后返回即可。

代码实现

classSolution{int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};bool vis[50][50];public:voiddfs(vector<vector<int>>& grid,int i,int j,int& cnt){++cnt; vis[i][j]=true;int m = grid.size();int n = grid[0].size();for(int k =0; k <4; k++){int x = i + dx[k];int y = j + dy[k];if(x >=0&& x < m && y >=0&& y < n && grid[x][y]==1&&!vis[x][y])dfs(grid, x, y, cnt);}}intmaxAreaOfIsland(vector<vector<int>>& grid){int ret =0, cnt =0;int 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&&!vis[i][j]){dfs(grid, i, j, cnt); ret =max(ret, cnt); cnt =0;}}}return ret;}};

四、被围绕的区域

题目解析

算法思路

将所有不在边缘区域的 O 全部修改成 X

• 先将在边缘的 O 区域进行标记（特殊处理，修改成其他无关字符）
• 再将所有没有标记的 O 全部修改成 X
• 最后，再复原边缘区域的 O

代码实现

classSolution{int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};bool vis[210][210];public:voiddfs(vector<vector<char>>& board,int i,int j,bool isChange =false){if(isChange) board[i][j]='X'; vis[i][j]=true;int m = board.size();int n = board[0].size();for(int k =0; k <4; k++){int x = i + dx[k];int y = j + dy[k];if(x >=0&& y >=0&& x < m && y < n &&!vis[x][y]&& board[x][y]=='O')dfs(board, x, y, isChange);}}voidsolve(vector<vector<char>>& board){// 处理边界int m = board.size(), n = board[0].size();for(int i =0; i < m; i++){if(board[i][0]=='O'&&!vis[i][0])dfs(board, i,0);if(board[i][n -1]=='O'&&!vis[i][n -1])dfs(board, i, n -1);}for(int i =0; i < n; i++){if(board[0][i]=='O'&&!vis[0][i])dfs(board,0, i);if(board[m -1][i]=='O'&&!vis[m -1][i])dfs(board, m -1, i);}// 修改内部for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(board[i][j]=='O'&&!vis[i][j])dfs(board, i, j,true);}}}};

本篇文章到这里就结束了，感谢支持
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws