C++ easy understanding BFS with comments


  • 0
    S

    //

    class Solution {
    public:
    void solve(vector<vector<char>>& board) {

        int row = board.size();
        if (row == 0) return;        
        std::vector< std::pair<int,int> > region;
        
        queue<std::pair<int,int> > que;
        
        int col = board[0].size();
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if (board[i][j] == 'O')
                {
                    bool live=false;
                    board[i][j] = 'T';
    
                    que.push(make_pair(i,j));
    
                    while( !que.empty() )
                    {
                        pair<int, int> tmp = que.front();
                        region.push_back(tmp);  //save the processing region
                        que.pop();
                        
                        if (tmp.first == 0 || tmp.second==0 || tmp.first == (row-1) || tmp.second==(col-1) )
                            live = true;  // if any 'O' is close to the boundary, the block is live
    
                        if ( (tmp.first-1) >= 0 && board[tmp.first-1][tmp.second] == 'O')
                        {
                            board[tmp.first-1][tmp.second] = 'T';
                            que.push(make_pair(tmp.first-1, tmp.second));
                        }
                        
                        if ( (tmp.first+1) < row && board[tmp.first+1][tmp.second] == 'O')
                        {
                            board[tmp.first+1][tmp.second] = 'T';
                            que.push(make_pair(tmp.first+1, tmp.second));
                        }                        
                    
                        
                        if ( (tmp.second-1) >= 0 && board[tmp.first][tmp.second-1] == 'O')
                        {
                            board[tmp.first][tmp.second-1] = 'T';
                            que.push(make_pair(tmp.first, tmp.second-1));
                        }                        
                        
                        if ( (tmp.second+1) >= 0 && board[tmp.first][tmp.second+1] == 'O')
                        {
                            board[tmp.first][tmp.second+1] = 'T';
                            que.push(make_pair(tmp.first, tmp.second+1));
                        }                        
                    }
    
                    if (!live)
                    {
                        for(int k=0; k<region.size(); k++)
                        {
                            board[region[k].first][region[k].second] = 'X';
                        }
                    }
                    region.clear();
                }
            }
        }
        
        
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if (board[i][j] == 'T')
                    board[i][j] = 'O' ;
            }
        }
    
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.