class Solution {
public:
    int m=0 , n=0;
    bool board_flag = false;
    int dir[4][2] = {0,-1,0,1,-1,0,1,0};
    void dfs(vector<vector<char>>& board ,  vector<vector<bool>> &path ,int x , int y ,bool exchange)
    {   
        for(int i=0 ; i<4 ;i++)
        {
            int next_x = x + dir[i][0];
            int next_y = y + dir[i][1];
            if(next_x<0 || next_x >= m || next_y<0||next_y>=n)
            {
                board_flag = true;
                continue;
            }
            if(exchange == false && board[next_x][next_y] == 'O' && path[next_x][next_y] == false)
            {
                path[next_x][next_y] = true;
                dfs(board,path,next_x,next_y,exchange);
            }
            if(exchange == true && board[next_x][next_y] == 'O')
            {
                board[next_x][next_y] = 'X';
                dfs(board,path,next_x,next_y,exchange);
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        vector<vector<bool>> path(m,vector<bool>(n,false));
        for(int i=0 ; i<m ;i++)
        {
            for(int j=0 ; j<n ;j++)
            {
                if(board[i][j] == 'O' && path[i][j] == false)
                {
                    board_flag = false;
                    path[i][j] = true;
                    dfs(board,path,i,j,false);
                    if(board_flag == false)
                    {
                        board[i][j] = 'X';
                        dfs(board,path,i,j,true);
                    } 
                }
            }
        }
    }
};