欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-130.被包围的区域、广度优先搜索

程序员文章站 2022-06-12 09:01:07
...

LeetCode-130.被包围的区域、广度优先搜索
来源:力扣(LeetCode)第130题

BFS 算法

广度优先搜索(BFS)的本质就是从源点出发,按层顺序进行遍历,把每一层的所有节点访问完后再转到下一层;
使用队列(queue)来记录将要访问的点,访问完每个点就出队,然后把它的邻近点入队;
同时要记录哪些点被访问过以避免重复访问。
对边界上的 O 进行 BFS 搜索,从而标记所有和边界相连的 O,然后再进行替换即可

题目分析

因为边界以及和边界相连的 O 不能被替换,可以对所有边界上的 O 进行广度优先搜索找到所有与其相连的 O 并做标记即可。
LeetCode-130.被包围的区域、广度优先搜索

代码示例

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if( board.size() == 0) return;
        queue<pair<int,int>> myqueue;
        // 边界上的 O 加入队列
        for(vector<int>::size_type j = 0;j < board[0].size();j++)
        {
            if( board[0][j] == 'O')
            {
                myqueue.push(make_pair(0,j));
            }
            if( board[board.size()-1][j] == 'O')
            {
                myqueue.push(make_pair(board.size()-1,j));
            }
        }
        for(vector<int>::size_type i = 1;i < board.size()-1;i++)
        {
            if( board[i][0] == 'O' )
            {
                myqueue.push(make_pair(i,0));
            }
            if( board[i][board[0].size()-1] ==  'O' )
            {
                myqueue.push(make_pair(i,board[0].size()-1));
            }
        }
        // BFS 一层层扩展
        while( !myqueue.empty())
        {
            auto cur = myqueue.front();myqueue.pop();
            int row = cur.first;
            int col = cur.second;
            board[row][col] = 'Q';
            if( col+1 < board[0].size() && board[row][col+1] == 'O')
            {
                myqueue.push(make_pair(row,col+1));
            }
            if( col -1 >= 0 && board[row][col-1] == 'O')
            {
                myqueue.push(make_pair(row,col-1));
            }
            if( row+1 < board.size() && board[row+1][col] == 'O')
            {
                myqueue.push(make_pair(row+1,col));
            }
            if( row -1 >= 0 && board[row-1][col] == 'O')
            {
                myqueue.push(make_pair(row-1,col));
            }
        }
        //替换字符
        for(vector<int>::size_type i = 0;i < board.size();i++)
        {
            for(vector<int>::size_type j = 0;j < board[0].size();j++)
            {
                if( board[i][j] == 'O') board[i][j] = 'X';
                else if( board[i][j] == 'Q' ) board[i][j] = 'O';

            }
        }
    }
};

LeetCode-130.被包围的区域、广度优先搜索