前言

上篇我们简要介绍了用BFS算法解决FloodFill问题，本篇我们将结合具体题目，进一步深化对于该算法的理解运用。

一. 图像渲染

1.1 题目链接：https://leetcode.cn/problems/flood-fill/description/

1.2 题目分析：

• 有一个m*n的二维数组表示图像，其中的值代表颜色
• 给出起始坐标和目标颜色，要求与起点相接并且值相同的所有像素点的值，都改为给定color的值
• 遍历方向为上下左右

1.3 思路讲解：

结合上篇内容很容易联想到使用bfs算法，但是在上下左右四个方向遍历时，可以通过初始化两个数组，大大简化步骤。

如图，将二维数组映射在平面直角坐标系内，上下左右四个方向的坐标变化如下。

之后我们按照层序遍历的方式，将各个顶点依次入队列，并按照上下左右的方向遍历判断即可。

1.4 代码实现：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int prev=image[sr][sc];
        int dx[]={0,0,-1,1};
        int dy[]={1,-1,0,0};
        int m=image.size();//行
        int n=image[0].size();//列
        if(prev==color)
        {
            return image;
        }//处理特殊情况
        queue<pair<int,int>> q;
        q.push({sr,sc});
        while(q.size())
        {
            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.1 题目链接：https://leetcode.cn/problems/number-of-islands/description/

2.2 题目分析：

• 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

• 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。（不考虑斜侧方向，只考虑水平和竖直）

• 此外，你可以假设该网格的四条边均被水包围。

2.3 思路讲解：

岛屿与上题的上色问题类似，都要求一个点内附近相接的同属性点。
通俗来讲，即一大块相接且被0围住的1，即代表一块岛屿。

因此，我们可以遍历数组内的每一个点，如果为1，则说明此处有一个岛屿，使用bfs算法将其周围的1全部转化为0

注意：本题并未提到原数组是否可以更改，因此我们为了以防万一，可以通过标记数组的方式进行1的转换。

2.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    bool vis[301][301]={0};
    int m,n;
    int ret=0;//岛屿数量
    void bfs(vector<vector<char>>& gird,int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        vis[i][j]=true;
        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&&vis[x][y]==0&&gird[x][y]=='1')
                {
                    q.push({x,y});
                    vis[x][y]=true;
                }
            }
        }
    }
    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'&&vis[i][j]==0)
                {
                    ret++;
                    bfs(grid,i,j);
                }
            }
        }
        return ret;
        
        
    }
};

三. 岛屿的最大面积

3.1 题目链接：https://leetcode.cn/problems/max-area-of-island/description/

3.2 题目分析：

• 岛屿的规则与上相同
• 本题要求返回岛屿的最大面积，而非岛屿的数量

3.3 思路讲解：

大体思路与上题相同，只需要记录下遍历过程中最大的岛屿面积，并在最终返回即可。

3.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    bool vis[51][51]={false};//标记数组
    int m,n;
    int ret=0;//最大面积
    int bfs(vector<vector<int>>& grid,int i,int j)
    {
        int count=1;//记录该岛屿面积
        queue<pair<int,int>> q;
        q.push({i,j});
        vis[i][j]=true;
        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]==0)
                {
                    q.push({x,y});
                    count++;
                    vis[x][y]=true;
                }
            }
        }
        return 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&&vis[i][j]==0)
                {
                    int temp=bfs(grid,i,j);
                    ret=max(ret,temp);
                }

            }
        }
        return ret;
        
    }
};

四. 被围绕的区域

4.1 题目链接：https://leetcode.cn/problems/surrounded-regions/description/

4.2 题目分析：

• 给定一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获所有被围绕的区域
• 围绕区域指被X包围的O
• 捕获指将O替换为X

4.3 思路讲解：

• 首先需要明确，最外层的O由于没有被X包围，因此是永远不会被替换的
• 因此被替换的只有边界内的O

所以我们只需要利用BFS算法遍历并替换即可。

注意：由于BFS算法在上下左右遍历时，可能存在边界上有O的情况，处理起来较为复杂。我们可以采取正难则反的思路。
在遍历之前，将边界上所有的O转化为*

4.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({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();
        //遍历最上和最下两行
        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O')
            {
                board[0][j]='*';
                bfs(board,0,j);
            }
            if(board[m-1][j]=='O')
            {
                board[m-1][j]='*';
                bfs(board,m-1,j);
            }

        }
        //遍历最左和最右两列
        for(int i=0;i<m;i++)
        {
            if(board[i][0]=='O')
            {
                board[i][0]='*';
                bfs(board,i,0);
            }
            if(board[i][n-1]=='O')
            {
                board[i][n-1]='*';
                bfs(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';
                }
            }
        }//还原操作


        
    }
};

小结

本篇关于BFS算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！