Easy dfs solution without visited matrix

amazon
Tags: #<Tag:0x00007f1827b5e140>

#1

void dfs(vector<vector> &A,int &count,int i,int j){
if(i<0||j<0||i>=A.size()||j>=A[0].size()||A[i][j]==0)
return ;

count++;

A[i][j]=0;
dfs(A,count,i+1,j);
dfs(A,count,i-1,j);
dfs(A,count,i,j+1);
dfs(A,count,i,j-1);
dfs(A,count,i+1,j-1);
dfs(A,count,i+1,j+1);
dfs(A,count,i-1,j-1);
dfs(A,count,i-1,j+1);

}
int Solution::solve(vector<vector > &A) {
int max=INT_MIN;
int n=A.size();
int m=A[0].size();
int i,j;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(A[i][j]==1)
{
int count =0;
dfs(A,count,i,j);
if(count>max)
max=count;
}
}
}
return max;
}