Easy DFS Approach


#1

int X[] = {0,1,0,-1};
int Y[] = {1,0,-1,0};

void dfs(vector A, int vis[][1001], int u, int v, int n ,int m){

if(u<0 or v<0 or u>=n or v>=m)return ;
if(vis[u][v] or A[u][v] == 'O')return ;

vis[u][v] = 1;

for(int i=0;i<4;i++){
    int l = u + X[i];
    int r = v + Y[i];
    
    dfs(A,vis,l,r,n,m);
}

}

int Solution::black(vector &A) {

int n = A.size();
int m = A[0].size();

int vis[1001][1001];
memset(vis,0,sizeof(vis));
int ans=0;
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(!vis[i][j] and A[i][j]=='X')
        {
            ans++;
            dfs(A,vis,i,j,n,m);
        }
    }
}
return ans;

}