欢迎来到Cefler的博客😁
🕌博客主页:那个传说中的man的主页
🏠个人专栏:题目解析
🌎推荐文章:【LeetCode】winter vacation training
前言
Flood-Fill算法
是一种图像处理算法,用于填充连通区域的颜色。它从给定的起始点开始,将所有与其相邻且具有相同颜色的区域标记为一个新的颜色。
以下是Flood-Fill算法的基本思想:
- 选择一个起始点和目标颜色,以及要填充的新颜色。
- 在起始点上应用目标颜色。
- 检查起始点的相邻区域,如果颜色与目标颜色相同,则将其标记为新颜色,并将其加入到处理队列中。
- 重复步骤3,直到队列为空。
- 当队列为空时,说明所有与起始点连通的区域都已经被填充为新颜色。
Flood-Fill算法可以使用递归或迭代的方式实现。
👉🏻图像渲染
原题链接:图像渲染
mycode:
class Solution {
public:
int dx[4] = {
0,0,1,-1};
int dy[4] = {
1,-1,0,0};
bool check[51][51];
int m,n,oldcolor;
void dfs(vector<vector<int>>& image, int sr, int sc, int color)
{
for(int k = 0;k<4;k++)
{
int x = dx[k]+sr,y = dy[k]+sc;
if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==oldcolor&&!check[x][y])
{
image[x][y] = color;
check[x][y] = true;
dfs(image,x,y,color);
//不需要恢复现场,是因为这些都是符合要求的方格,只要符合了填上了就没错,所以不需要销毁
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
m = image.size(),n = image[0].size();
oldcolor = image[sr][sc];
image[sr][sc] = color;
check[sr][sc] = true;
dfs(image,sr,sc,color);
return image;
}
};
👉🏻岛屿数量
原题链接:岛屿数量
mycode:
class Solution {
public:
int dx[4] = {
0,0,1,-1};
int dy[4] = {
1,-1,0,0};
bool check[301][301];
int m,n;
int count = 0;
void dfs(vector<vector<char>>& grid,int i,int j)
{
for(int k = 0;k<4;k++)
{
int x = dx[k]+i,y = dy[k]+j;
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&!check[x][y])
{
check[x][y] = true;
dfs(grid,x,y);
//不需要恢复现场,是因为这些都是符合要求的方格,只要符合了填上了就没错,所以不需要销毁
}
}
}
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])
{
check[i][j] = true;
dfs(grid,i,j);
count++;
}
}
}
return count;
}
};
👉🏻岛屿的最大面积
原题链接:岛屿的最大面积
mycode:
class Solution {
public:
int dx[4] = {
0,0,1,-1};
int dy[4] = {
1,-1,0,0};
bool check[301][301];
int m,n;
int count = 0;
void dfs(vector<vector<int>>& grid,int i,int j,int& area)
{
for(int k = 0;k<4;k++)
{
int x = dx[k]+i,y = dy[k]+j;
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&!check[x][y])
{
check[x][y] = true;
area++;
dfs(grid,x,y,area);
//不需要恢复现场,是因为这些都是符合要求的方格,只要符合了填上了就没错,所以不需要销毁
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(),n = grid[0].size();
int max = 0;
for(int i = 0;i<m;i++)
{
for(int j = 0;j<n;j++)
{
if(grid[i][j]==1&&!check[i][j])
{
check[i][j] = true;
int area = 1;
dfs(grid,i,j,area);
if(area>max) max = area;
}
}
}
return max;
}
};