Capture Regions on Board

• Time : O(nm)
• Space : O(nm)

void bfs(vector<vector<char>>& A, int sy, int sx) {
    int n = A.size(), m = A[0].size();
    int dy[4]{-1,0,1,0},dx[4]{0,1,0,-1};
    queue<pair<int,int>> q;
    q.push({sy,sx});
    A[sy][sx] = '#';
    while(!q.empty()) {
        auto [y,x] = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if(0 <= ny and ny < n and 0 <= nx and nx < m and A[ny][nx] == 'O') {
                q.push({ny,nx});
                A[ny][nx] = '#';
            }
        }
    }
}

void Solution::solve(vector<vector<char>> &A) {
    int n = A.size(), m = A[0].size();
    for(int i = 0; i < n; i++) {
        if(A[i][0] == 'O') bfs(A,i,0);
        if(A[i][m-1] == 'O') bfs(A,i,m-1);
    }
    for(int i = 0; i < m; i++) {
        if(A[0][i] == 'O') bfs(A,0,i);
        if(A[n-1][i] == 'O') bfs(A,n-1,i);
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(A[i][j] == 'O') A[i][j] = 'X';
            else if(A[i][j] == '#') A[i][j] = 'O';
        }
    }
}