Surrounded Regions

class Solution {
public:
vector<pair<int,int>> adj[40000][40000];
map<pair<int,int>,bool> vis;
int n,m;

bool check (int j, int i, int n, int m,vector<vector<char>>& board) {
    if (i<n && i>=0 && j<m && j>=0 && board[i][j] == 'O') return true;
    return false;
}

void dfs(pair<int,int> cur) {
    if (vis[{cur.first,cur.second}]) return;
    vis[{cur.first,cur.second}] = 1;
    for (auto ch : adj[cur.first][cur.second]) {
        if (!vis[{ch.first,ch.second}]) {
            dfs(ch);
        }
    }
}

void add_edges(int i, int j,vector<vector<char>>& board) {
    int dr[4] = {1,-1,0,0};
    int dc[4] = {0,0,-1,1};

    for (int k=0;k<4;k++) {
        if (check(i+dr[k], j+dc[k],n,m,board))
            adj[i][j].push_back({i+dr[k],j+dc[k]}), adj[i+dr[k]][j+dc[k]].push_back({i,j});
    }
}


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

    vector<pair<int,int>> nodes;

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (board[i][j] == 'O') {
                if (i==0 || j == 0 || i == n || j == m) nodes.push_back({i,j});
                add_edges(i,j,board);
            }
        }
    }

    for (auto cur : nodes) {
        dfs(cur);
    }

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

    }
};