Saturday, September 29, 2012

Counting discrete clusters of 1 in a binary 2D matrix


#include<iostream>
using namespace std;
int main()
{
int A[100][100];
int m,n;
void fun(int A[][100],int i,int j,int c,int m,int n);
cin>>m>>n;
int c=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>A[i][j];
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(A[i][j]>0)
{
c++;
fun(A,i,j,c,m,n);
}
}
}
cout<<c<<endl;
return 0;
}
void fun(int A[][100],int i,int j,int c,int m,int n)
{
A[i][j]=-1*c;
if(i>0 && j>0 && A[i-1][j-1]>0)
{
fun(A,i-1,j-1,c,m,n);
}
if(i>0 && j>=0 && j<n && A[i-1][j]>0)
{
fun(A,i-1,j,c,m,n);
}
if(i>0 && j<n-1 && A[i-1][j+1]>0)
{
fun(A,i-1,j+1,c,m,n);
}
if(i>=0 && i<n && j<n-1 && A[i][j+1]>0)
{
fun(A,i,j+1,c,m,n);
}
if(i<n-1 && j<n-1 && A[i+1][j+1]>0)
{
fun(A,i+1,j+1,c,m,n);
}
if(i<n-1 && j<n && j>=0 && A[i+1][j]>0)
{
fun(A,i+1,j,c,m,n);
}
if(i<n-1 && j>0 && A[i+1][j-1]>0)
{
fun(A,i+1,j-1,c,m,n);
}
if(i<n && i>=0 && j>0 && A[i][j-1]>0)
{
fun(A,i,j-1,c,m,n);
}
}
Sample Input:
3 5
1 1 1 0 0
0 0 1 0 1
0 1 0 1 1

Output:
1

No comments:

Post a Comment