Explanation:
Connected
set can be defined as group of cell(s) which has 1 mentioned on it and have at
least one other cell in that set with which they share the neighbor
relationship. A cell with 1 in it and no surrounding neighbor having 1 in it
can be considered as a set with one cell in it. Neighbors can be defined as all
the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E ,
S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.
Input
format :
First
line of the input contains T , number of test-cases.
Then
follow T testcases. Each testcase has given format.
N [
representing the dimension of the matrix N X N ].
Followed
by N lines , with N numbers on each line.
Ouput
format :
For
each test case print one line , number of connected component it has.
Sample
Input :
4
4
0 0
1 0
1 0
1 0
0 1
0 0
1 1
1 1
4
1 0
0 1
0 0
0 0
0 1
1 0
1 0
0 1
5
1 0
0 1 1
0 0
1 0 0
0 0
0 0 0
1 1
1 1 1
0 0
0 0 0
8
0 0
1 0 0 1 0 0
1 0
0 0 0 0 0 1
0 0
1 0 0 1 0 1
0 1
0 0 0 1 0 0
1 0
0 0 0 0 0 0
0 0
1 1 0 1 1 0
1 0
1 1 0 1 1 0
0 0
0 0 0 0 0 0
Sample
output :
1
3
3
9
Constraint
:
0
< T < 6
0
< N < 1009
=================WORKING CODE=================
#include<stdio.h>
int count_connected_set(int A[1015][1015],int i,int j,int n)
{
A[i][j]=2;
if(A[i-1][j-1]==1 && i>0 && j>0 && i<=n && j<=n ) //NW
count_connected_set(A,i-1,j-1,n);
if(A[i-1][j]==1 && i>0 && j>0 && i<=n && j<=n) //N
count_connected_set(A,i-1,j,n);
if(A[i-1][j+1]==1 && i>0 && j>0 && i<=n && j<=n)// //NE
count_connected_set(A,i-1,j+1,n);
if(A[i][j-1]==1 && i>0 && j>0 && i<=n && j<=n) //W
count_connected_set(A,i,j-1,n);
if(A[i][j+1]==1 && i>0 && j>0 && i<=n && j<=n) //E
count_connected_set(A,i,j+1,n);
if(A[i+1][j-1]==1 && i>0 && j>0 && i<=n && j<=n) //SW
count_connected_set(A,i+1,j-1,n);
if(A[i+1][j]==1 && i>0 && j>0 && i<=n && j<=n) //S
count_connected_set(A,i+1,j,n);
if(A[i+1][j+1]==1 && i>0 && j>0 && i<=n && j<=n) //SE
count_connected_set(A,i+1,j+1,n);
return 1;
}// end of count_connected_set()
int main()
{
int i,j,t,k,n,A[1015][1015],count;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]); // geting input a test case;
count =0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(A[i][j]==1)
if(count_connected_set(A,i,j,n))
count++;
}// of for
printf("%d\n",count);
}// end of while
return 0;
}
Let me know your thoughts.
