Share my C++ solution with explanation, very easy to understand


  • 1
    V
    • checking from the element on the edge, find all 'O's that not belong to the regions surrounded by 'X'
    • change these 'O' to 'Y', then the remaining 'O's are in the regions surrounded by 'X'
    • finally, change all 'O's to 'X's, and change all 'Y's to 'O's

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int row = board.size();
            if (row == 0)
                return;
            int col = board[0].size();
            if (col == 0)
                return;
    
            for (int i = 0; i < col; i++)
            {
                if (board[0][i] == 'O')//the first row
                    bfs(board, 0, i, row, col);
                
                if (board[row-1][i] == 'O')//the last row
                    bfs(board, row-1, i, row, col);
            }
            
            for (int i = 0; i < row; i++)
            {
                if (board[i][0] == 'O')//the first col
                    bfs(board, i, 0, row, col);
                    
                if (board[i][col-1] == 'O')//the last col 
                    bfs(board, i, col-1, row, col);
            }
            
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (board[i][j] == 'O')
                        board[i][j] = 'X';
                        
                    if (board[i][j] == 'Y')
                        board[i][j] = 'O';
                }
            }
            
        }
        
        void bfs(vector<vector<char>>& board, int x, int y, int row, int col)
        {
            if (x < 0 || x >= row || y < 0 || y >= col)
                return;
            
            board[x][y] = 'Y';
            
            queue<int> q;
            q.push(x);
            q.push(y);
            int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//up-down-left-right
            
            while (!q.empty())
            {
                int next_x = 0;
                int next_y = 0;
                
                x = q.front();
                q.pop();
                y = q.front();
                q.pop();
                
                for (int i = 0; i < 4; i++)
                {
                    next_x = x + dir[i][0];
                    next_y = y + dir[i][1];
                    
                    if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < col && board[next_x][next_y] == 'O')
                    {
                        board[next_x][next_y] = 'Y';
                        q.push(next_x);
                        q.push(next_y);
                    }
                }
            }
        }
    };
    

Log in to reply
 

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