Simple BFS graph traversal


#1

void dfs(vector &A,int i,int j)
{
A[i][j]=‘O’;
if(i>0 && A[i-1][j]==‘X’)
dfs(A,i-1,j);
if(i<(A.size()-1) && A[i+1][j]==‘X’)
dfs(A,i+1,j);
if(j>0 && A[i][j-1]==‘X’)
dfs(A,i,j-1);
if(j+1<A[i].size() && A[i][j+1]==‘X’)
dfs(A,i,j+1);
}
int Solution::black(vector &input) {
if(input.size()==0)
{
return 0;
}

int sol=0;
for(int i=0;i<input.size();i++)
{
    for(int j=0;j<input[0].size();j++)
    {
        if(input[i][j]=='X')
        {
            dfs(input,i,j);
            sol++;
        }
    }
}
return sol;

}