Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.
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
plz explain the test cases …its difficult the get …???
in the 1st test case all the 1s are connected…taking 0 based index…the 1 at 0,2 is connected to 1,2 which is connected to 2,1(diagonally) which is connected to 1,0(diagonally) and 3,0(diagonally) 3,1 3,2(diagonally) and 3,2 is connected to 3,3…hence all 1s are connected hence only 1 connected component…in the 2nd case 1 at 0,0 is 1 connected component and at 0,3 is another…and the 3rd component is 3,0->2,1->2,2->3,3…so ans is 3…now see if u can understand the next 2 cases…hope this helps…
btw…where is this problem from???
By connected Cells it means all the cells which are connected to each other…
e.g in the first test case consider the indexes as starting from 1 to 4 and its a 4 vs 4 matrix
consider the 1s in this matrix… all the 1s are connected to each other as neighbours. You can take a pencil and while starting from any position containing a 1 you go on marking all 1s in its neighbourhood and continue to do so as long as its possible.You can see that you end up marking all the 1s. So basically all these 1s are connected and lie in a single connected set.
however in the second test case,the top row two corner 1s are totally disconnected from the other 1;s hence two disconnected 1s plus the rest are all a single connected set=3
//Recursive Solution
#include
using namespace std;
int var=1;
int fun(int i,int j,int a[][100],int n)
{
if(a[i][j]==1 && i>=0 && j>=0 && i<n && j<n)
{
a[i][j]=var;
fun(i-1,j-1,a,n);
fun(i-1,j,a,n);
fun(i-1,j+1,a,n);
fun(i,j-1,a,n);
fun(i,j+1,a,n);
fun(i+1,j-1,a,n);
fun(i+1,j,a,n);
fun(i+1,j+1,a,n);
}
}
int main()
{
int n,a[100][100];
int t;
cin>>t;
while(t–)
{
var=1;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
// cout<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]==1)
{
var+=1;
fun(i,j,a,n);
}
}
}
int small=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]>small)
small=a[i][j];
//cout<<a[i][j]<<" ";
}
// cout<<endl;
}
cout<<small-1<<endl;;
}
// cin>>n;
return 0;
}