class Solution {
public:
    void dfs(vector<vector<char>>& board, int i, int j, char c) {
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O') return;
        board[i][j] = c;
        dfs(board, i-1, j, c);
        dfs(board, i+1, j, c);
        dfs(board, i, j-1, c);
        dfs(board, i, j+1, c);
    }

    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();

        for(int i = 0; i < m; i++) {
            if(board[i][0] == 'O') dfs(board, i , 0, 'A');
            if(board[i][n-1] == 'O') dfs(board, i, n-1, 'A');
        }

        for(int j = 0; j < n; j++) {
            if(board[0][j] == 'O') dfs(board, 0, j, 'A');
            if(board[m-1][j] == 'O') dfs(board, m-1, j, 'A');
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'A') {
                    board[i][j] = 'O';
                }
            }
        }

    }
};