BFS解决FloodFill算法：（Leetcode：130. 被围绕的区域）

题目链接：130. 被围绕的区域 - 力扣（LeetCode）

BFS算法通常是边搜索边修改，所以当搜索到边界O时，前面的本不应该修改的数据已经被修改，所以按照正常顺序进行BFS搜索是行不通的。

正难则反，先用BFS搜索所有边界O，将这些边界O标记，剩下的所有未被标记的O就是需要修改的。最后重新遍历数据，找到未被标记的O并将它们修改为X即可。

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m=0,n=0;
    vector<vector<bool>> vis;
    void solve(vector<vector<char>>& board) {
        m=board.size();
        n=board[0].size();
        vis.resize(m);
        for(int i=0;i<m;++i)
        {
            vis[i].resize(n);
            for(int j=0;j<n;++j)
            {
                vis[i][j]=false;
            }
        }
        //边界位置进行广度优先搜索
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                //广度优先搜索
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O' && !vis[i][j])
                    bfs(board, i, j);
            }
        }
        //重新遍历数组
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(board[i][j]=='O'&&!vis[i][j]) board[i][j]='X';
            }
        }   
    }
    //广度优先搜索
    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        vis[i][j]=true;
        while(q.size())
        {
            int a=q.front().first;
            int b=q.front().second;
            q.pop();
            for(int k=0;k<4;++k)
            {
                int x=a+dx[k];
                int y=b+dy[k];
                if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O'&&!vis[x][y])
                {
                    q.push({x,y});
                    vis[x][y]=true;
                }
            }
        }
    }
};

原文地址：https://blog.csdn.net/2301_76197086/article/details/138116739

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！