Surrounded Regions

//130

Given a 2D board containing 'X' and 'O' (the letter 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

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
class Solution {
private:
    int m,n;
    queue<pair<int,int>> q;
    vector<vector<bool> >visited;
    int move[4][4]={{0,1},{0,-1},{1,0},{-1,0}};

    bool inArea(int x,int y){
        return x>=0 && x<m &&y>=0 && y<n;
    }
    void bfs(vector<vector<char>>& board){
        //first row
        for(int j=0;j<n;j++){
            if(board[0][j]=='O'){
                board[0][j]='B';
                visited[0][j]=true;
                q.push(make_pair(0,j));
            }
        }

        for(int j=0;j<n;j++){
            if(board[m-1][j]=='O'){
                board[m-1][j]='B';
                visited[m-1][j]=true;
                q.push(make_pair(m-1,j));
            }
        }

        for(int i=1;i<m-1;i++){
            if(board[i][0]=='O'){
                board[i][0]='B';
                visited[i][0]=true;
                q.push(make_pair(i,0));
            }
        }

        for(int i=1;i<m-1;i++){
            if(board[i][n-1]=='O'){
                board[i][n-1]='B';
                visited[i][n-1]=true;
                q.push(make_pair(i,n-1));
            }
        }
        if(q.empty()){
            return;
        }
        while(! q.empty()){
            pair<int,int> front=q.front();
            int x=front.first;
            int y=front.second;
            q.pop();
            for(int i=0;i<4;i++){
                int newx=x+move[i][0];
                int newy=y+move[i][1];
                if(inArea(newx,newy) && !visited[newx][newy] 
                    && board[newx][newy]=='O'){
                    //add queue
                    board[newx][newy]='B';
                    q.push(make_pair(newx,newy));
                    visited[newx][newy]=true;
                }
            }
        }
    }
public:
    
    void solve(vector<vector<char>>& board) {

        m=board.size();
        if(m==0){
            return;
        }
        n=board[0].size();
        
        visited=vector<vector<bool>>(m,vector<bool>(n,false));
        bfs(board);
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[i].size();j++){
                //boarx[i][j]=='X',no need change value
                //boarx[i][j] only one state;if() if() judge 2
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }else if(board[i][j]=='B'){
                    board[i][j]='O';
                }

            }
        }

    }
};

int main(){
    int m=4;
    int n=4;
    int arr[m][n]={{'X','X','X','X'},
    {'X','O','O','X'},
    {'X','O','O','X'},
    {'X','O','O','X'}};
    
    // int arr[1][1]={'X'};
    vector<vector<char>> board(m,vector<char>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            board[i][j]=arr[i][j];
        }
    }
    Solution().solve(board);
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}