【FloodFill算法】DFS

欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：【LeetCode】winter vacation training

---

前言
Flood-Fill算法是一种图像处理算法，用于填充连通区域的颜色。它从给定的起始点开始，将所有与其相邻且具有相同颜色的区域标记为一个新的颜色。

以下是Flood-Fill算法的基本思想：

1. 选择一个起始点和目标颜色，以及要填充的新颜色。
2. 在起始点上应用目标颜色。
3. 检查起始点的相邻区域，如果颜色与目标颜色相同，则将其标记为新颜色，并将其加入到处理队列中。
4. 重复步骤3，直到队列为空。
5. 当队列为空时，说明所有与起始点连通的区域都已经被填充为新颜色。

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