C++ dfs solution clean


#1

int n ,m;
vector x={-1,1,0,0};
vector y={0,0,-1,1};
bool check(int i,int j){
if(i<0 or i>=n or j<0 or j>=m) return false;
return true;
}
void dfs(int i,int j,vector<vector>& dp,vector& A,int cnt){
if(dp[i][j]!=-1 or A[i][j]==‘O’)
return;
dp[i][j]=cnt;
for(int p=0;p<4;p++){
if(check(i+x[p],j+y[p])){
dfs(i+x[p],j+y[p],dp,A,cnt);
}
}
}
int Solution::black(vector &A) {
n=A.size(),m=A[0].size();
vector<vector> dp(n+1,vector(m+1,-1));
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dp[i][j]==-1 and A[i][j]==‘X’){
// cout<<i<<’ '<<j<<endl;
cnt++;
dfs(i,j,dp,A,cnt);
}
}
}
return cnt;
}