class Solution {
public:
    vector<vector<char>> solve(vector<vector<char>>& board) {
        //NXM grid
        int N = board.size();
        int M = board[0].size();
        vector<vector<char>> values(N,vector<char>(M,'X'));
         vector<vector<int>> visited(N,vector<int>(M,0));
        queue<pair<int,int>> q;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {

                //If its a boundary O, mark all of it as unchangeable via bfs
                if(i==0 or j==0 or i==N-1 or j==M-1) {

                    if(board[i][j]=='O' && visited[i][j]==0) {
                        //We have not processed it. add it to the queue
                        //we run bfs
                        visited[i][j]=1;
                        values[i][j]='O';
                        q.push({i,j});
                        while(q.empty()==false) {
                            auto temp = q.front();
                            q.pop();
                            int r = temp.first;
                            int c = temp.second;
                            vector<pair<int,int>> dirs = {{r+1,c},{r-1,c},{r,c+1},{r,c-1}};
                            for(auto dir:dirs) {
                                //Validation check

                                int rn = dir.first;
                                int cn = dir.second;

                                if(rn<0 or rn>=N or cn<0 or cn>=M) { continue;}

                                if(board[rn][cn]=='O' && visited[rn][cn]==0) {
                                    q.push({rn,cn});
                                    visited[rn][cn]=1;
                                    values[rn][cn]='O';
                                }

                            }

                        }

                    }

                }
            }

        }

            return values;
    }
};