BFS解决FloodFill问题（Leetcode，733.图像渲染，200.岛屿数量，130.被围绕的区域）

 利用宽度优先搜索的方法结合列表解决数组中的相同元素区域性问题， 找到满足条件的位置后开始BFS若周围有满足条件的点，继续BFS直到周围没有满足条件的点。下面三道题分别是修改区域元素内容，寻找有多少个满足条件的区域和修改特定位置的区域元素内容。思路上是相同的，只有细微的差别。

733.图像渲染 

LeetCode，733.图像渲染

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
   
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int m = image.size(),n=image[0].size();
    
    int pre=image[sr][sc];//记录选定位置颜色
    if(pre==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(y<n&&x<m&&y>=0&&x>=0&&image[x][y]==pre)
            {
                q.push({x,y});
                //若满足条件则将该坐标加入队列中以便继续搜索
            }
        }
    }
    return image;
    }
};

200.岛屿数量

LeetCode，200.岛屿数量

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool vim[301][301]={false};
    //用于判定该位置是否搜索过，false为没有，true为搜索过
   
    int numIslands(vector<vector<char>>& grid) {
        int 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'&&vim[i][j] ==false)
                {
                    ret++;
                    floodFill(grid,i,j);
                    //在遍历过程中找到岛屿之后开始BFS
                    //floodFill能将邻接的位置全部标记为已经搜索过
                }
            }
        }
 
        return ret;
    }
   
    void floodFill(vector<vector<char>>& image, int sr, int sc) {
    int m = image.size(),n=image[0].size();
    if(image[sr][sc]=='0') return ;
    queue<pair<int,int>> q;
    q.push({sr,sc});
    //先将当前位置加入队列
    while(q.size())
    {
        
        auto[a,b]=q.front();
        q.pop();
        //获取开头位置然后将该位置删除
        
        vim[a][b]=true;
        //表示已经搜索过
        
        for(int i = 0;i<4;i++)
        {
            int x = a+dx[i],y = b+dy[i];//获取四周位置坐标
            if(y<n&&x<m&&y>=0&&x>=0&&image[x][y]=='1'&&vim[x][y]!=true)
            {
                q.push({x,y});
                vim[x][y]=true;
                //标记位置
            }
        }
    }
    return ;
    }
 
};

130.被围绕的区域 

LeetCode，130.被围绕的区域

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    void solve(vector<vector<char>>& board) {
        int m = board.size(),n = board[0].size();
        
        接下来两个for循环的目的是将与边缘位置相连的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 i = 0;i<m;i++)
        {
            if(board[i][0]=='O')bfs(board,i,0,'*');
            if(board[i][n-1]=='O')bfs(board,i,n-1,'*');
        } 
 
    //遍历处理后的数组，若为O则为被X包围的，变为X，若为*则为原先与边缘相连的O，再将其还原为O   
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<n;j++)
        {
            if(board[i][j]=='*') board[i][j]='O';
            else if(board[i][j]=='O') board[i][j]='X';
        }        
    }
    return ;
    }
    
    //从i，j位置开始，将与i,j相同且相连的一片区域内的元素变为符号 s
    void bfs(vector<vector<char>>& board,int i ,int j ,char s)
    {
        int m = board.size(),n = board[0].size();
        queue<pair<int,int>>q;
        q.push({i,j});
        board[i][j]=s;
        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]=s;
                }
            }
        }
        return ;
    }
 
};

以上就是三道题的代码，笔者认为注释已经很清楚了，尤其是第一道的代码注释，建议这三道题一块去做，更容易理解BFS去解决这类型的问题。

欢迎大家在评论区交流讨论，批评指正。