130 Surrounded Regions

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.size()<=1 || board[0].size()<=1)
            return;
        for (int j=0;j<board[0].size();j++)
        {
            if (board[0][j]=='O')
            {
                board[0][j]='Y';
                check(board,0,j);
            }
        }
        for (int j=0;j<board[0].size();j++)
        {
            if (board[board.size()-1][j]=='O')
            {
                board[board.size()-1][j]='Y';
                check(board,board.size()-1,j);
            }
        }
        for (int i=1;i<board.size()-1;i++)
        {
            if (board[i][0]=='O')
            {
                board[i][0]='Y';
                check(board,i,0);
            }
        }
        for (int i=1;i<board.size()-1;i++)
        {
            if (board[i][board[0].size()-1]=='O')
            {
                board[i][board[0].size()-1]='Y';
                check(board,i,board[0].size()-1);
            }
        }
        
        for (int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if (board[i][j]=='Y')
                    board[i][j]='O';
                else if (board[i][j]=='O')
                    board[i][j]='X';
            }
        }
    }
    void check(vector<vector<char>> &board,int i,int j)
    {
        if (i-1>0 && board[i-1][j]=='O')
        {
            board[i-1][j]='Y';
            check(board,i-1,j);
        }
        if (i+1<board.size() && board[i+1][j]=='O')
        {
            board[i+1][j]='Y';
            check(board,i+1,j);
        }
        if (j-1>0 && board[i][j-1]=='O')
        {
            board[i][j-1]='Y';
            check(board,i,j-1);
        }
        if (j+1<board[0].size() &&board[i][j+1]=='O')
        {
            board[i][j+1]='Y';
            check(board,i,j+1);
        }
    }
};