Simple Depth First Search


#1
bool vis[1001][1001];
void dfs(int i,int j,int n,int m,vector<string> &A){
    if(i>=0 && j>=0 && i<=n && j<=m && A[i][j]=='X' && !vis[i][j]){
        vis[i][j]=1;
        dfs(i+1,j,n,m,A);
        dfs(i,j+1,n,m,A);
        dfs(i-1,j,n,m,A);
        dfs(i,j-1,n,m,A);
    }
}
int Solution::black(vector<string> &A) {
    int n=A.size();
    int m=A[0].size();
    int count=0;
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
        if(!vis[i][j] && A[i][j]=='X'){
            dfs(i,j,n,m,A);
            count++;
        }
        }
    }
    return count;
}