9ms, C++ BFS solution


  • 0

    In order to find all surrounded region, we could first find the region that is not surrounded and mark those regions, then the left region is the surrounded regions that we wanted. In order to find the region that is not surrounded, we should start with the '0' at four borders, then do BFS, then we mark all the 'O' that is not surrounded with "C", then we need to scan the board again, change 'C' to 'O', and change 'O' to 'X';

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int m = board.size();
            int n = m ? board[0].size() : 0;
            if(m <= 2 || n <= 2)
                return ;
            vector<pair<int,int>> row;
            vector<pair<int,int>> col;
            row.push_back(make_pair(0,1)); col.push_back(make_pair(0,n));
            row.push_back(make_pair(m-1,m)); col.push_back(make_pair(0,n));
            row.push_back(make_pair(0,m)); col.push_back(make_pair(0,1));
            row.push_back(make_pair(0,m)); col.push_back(make_pair(n-1,n));
            int delta[] = {0,1,0,-1,0};
           
            for(int index = 0;index < 4;index++)
            {
                for(int i = row[index].first;i < row[index].second;i++)
                {
                    for(int j = col[index].first;j < col[index].second;j++)
                    {
                        if(board[i][j] == 'O')
                        {
                            queue<pair<int,int>> q;
                            q.emplace(i,j);
                            board[i][j] = 'C';
                            while(!q.empty())
                            {
                                auto pos = q.front();
                                q.pop();
                                for(int ix = 0;ix < 4;ix++)
                                {
                                    int r = pos.first + delta[ix];
                                    int c = pos.second + delta[ix+1];
                                    if(r >= 0 && r < m && c >= 0 && c < n && board[r][c] == 'O')
                                    {
                                        board[r][c] = 'C';
                                        q.emplace(r,c);
                                    }
                                }
                                
                            }
                        }
                    }
                }
            }
            for(int i = 0;i < m;i++)
            {
                for(int j = 0;j < n;j++)
                {
                    if(board[i][j] == 'C')
                        board[i][j] = 'O';
                    else if(board[i][j] == 'O')
                        board[i][j] = 'X';
                }
            }
            
        }
    };
    

Log in to reply
 

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