前面我们已经学习了用队列和优先级队列解决宽度优先算法的问题。本期我们就来利用BFS算法解决另一个重要的模型——FloodFill问题。

        相关代码已经上传至作者的个人gitee：楼田莉子/C++算法学习喜欢请点个赞谢谢

目录

FloodFill问题介绍

1、图像渲染

2、岛屿数量

3、岛屿的最大面积

4、被围绕的区域

---

FloodFill问题介绍

        在解决算法题之前我们需要了解什么是FloodFill问题。

        FloodFill问题中文直译就是“洪水灌溉”问题。

        如下图所示，这是一块田地。

        它并不是一马平川的，而是凹凸不平的。就像下图所示，正数表示突起，负数表示凹陷

        洪水来临的时候会把凹下去的位置填满水，突起的地方不会，被包围的地方不会（本图里没有展示）

        本质上就是找到性质相同的连通块。        

1、图像渲染

        算法思想：BFS

        

        向量数组：

        

class Solution {
public:
    typedef pair<int ,int> PI;
    //向量数组
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {    
        int m=image.size(),n=image[0].size();
        int prev=image[sr][sc];//标记要修改的像素值
        if(prev==color) return image;
        queue<PI>q;
        q.push({sr,sc});
        while(!q.empty())
        {
            auto [a,b]=q.front();
            q.pop();
            image[a][b] =color;
            //遍历四个方向
            for(int i=0;i<4;i++)
            {
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)
                {
                    q.push({x,y});
                }
            }
        }   
        return image;
    }
};

2、岛屿数量

        算法思路：

        算法一：修改原有数组

        不过这个思路需要斟酌，因为力扣提供的是一个接口的形式，面试的时候需要询问是否可以修改，如果可以才可以使用

        算法二：搞一个vis数组，为bool类型，存储true和false。如果遍历过则为true反之为false

class Solution {
public:
    //向量数组
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    //vis数组
    bool vis[301][301];
    int m,n;
    void bfs(vector<vector<char>>& grid,int i,int j)
    {
        queue<pair<int ,int>>q;
        q.push({i,j});
        vis[i][j]=true;
        while(!q.empty())
        {
            auto [a,b]=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&vis[x][y]==false)
                {
                    q.push({x,y});
                    vis[x][y]=true;
                }
            }
        }   
    }
    int numIslands(vector<vector<char>>& grid) 
    {
        m=grid.size(),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]==false)
                {
                    ret++;
                    bfs(grid,i,j);
                }
                
            }
        }
        return ret;
    }
};

3、岛屿的最大面积

         算法思想：

class Solution {
    //向量数组
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    //vis数组
    bool vis[51][51];
    int m, n;
public:

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

4、被围绕的区域

        算法思想：

        1、先扫描边界上的O区域

        2、扫描矩阵，还原即可

class Solution {
    //向量数组
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
public:
    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<pair<int ,int >>q;
        q.push({i,j});
        board[i][j]='.';
         while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n
                    && board[x][y]=='O')
                {
                    q.push({ x, y });
                    board[x][y]='.';
                }
            }
        }
    }
    void solve(vector<vector<char>>& board) 
    {
        m=board.size(),n=board[0].size();
        //先处理边界上的’O‘，然后转换成'.'
        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 j=0;j<m;j++)
        {
            if(board[j][0]=='O') bfs(board,j,0);
            if(board[j][n-1]=='O') bfs(board,j,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';
                if(board[i][j]=='.') board[i][j]='O';
            }
        }
    }
};

        本期内容就到这里了，喜欢请点个赞谢谢。