Black Shapes

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

void bfs(vector<string>& A, int sy, int sx) {
    A[sy][sx] = 'O';
    queue<pair<int,int>> q;
    q.push({sy,sx});
    int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
    int n = A.size(), m = A[0].size();
    while(q.size()) {
        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] == 'X') {
                A[ny][nx] = 'O';
                q.push({ny,nx});
            }
        }
    }
}
int Solution::black(vector<string> &A) {
    int res = 0;
    for(int i = 0; i < A.size(); i++) {
        for(int j = 0; j < A[i].length(); j++) {
            if(A[i][j] == 'X') {
                res += 1;
                bfs(A,i,j);
            }
        }
    }
    return res;
}