Grouping 1's in a matrix into clusters - C++

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define N 7
using namespace std;
vector<vector<int>> vec(N,vector<int>(N));
vector<vector<pair<int,int>>> vecD(N,vector<pair<int,int>>(N,{0,0}));
vector<vector<bool>> visited(N,vector<bool>(N,false));
int clusters=0;
int ones=0;
void init(){
	srand(time(NULL));
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			vec[i][j] = rand()%2;
			if(vec[i][j]==1)
				ones++;
			cout << vec[i][j] << "\t";
		}
		cout << endl;
	}
	for(int i=0;i<50;i++)
		cout << "-";
	cout << endl;
}
void print(){
	cout << "Co-ordinates:\n";
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cout << "{"<<i<<", "<<j<<"}: "<< vec[i][j]<<"\t";
		}
		cout << endl;
	}
}
void printQQ(){
	for(int i=0;i<50;i++)
		cout << "-";
	cout << endl ;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(visited[i][j]==true){
				cout << "Q"<<"\t";
			}
			else{
				cout << "*\t";
			}
		}
		cout << endl;
	}
	cout << endl;
}
void printQ(){
	for(int i=0;i<50;i++)
		cout << "-";
	cout << endl;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(vecD[i][j].first!=0){
				cout << "("<<vecD[i][j].first<<","<<vecD[i][j].second<<")"<<"\t";
			}
			else{
				cout << "*\t";
			}
		}
		cout << endl;
	}
}
bool isOne(int x,int y){
	if(vec[x][y]==1)
		return true;
	return false;
}
bool isSafe(int x,int y){
	if(x<0 || x>=N || y<0 || y>=N)
		return false;
	return true;
}
int findPath(int x,int y){
	int cntt=1;
	if(visited[x][y]==true || vec[x][y]==0)
		return 0;
	else{
		visited[x][y]=true;
		//x,y-1 Left
		if(isSafe(x,y-1) && isOne(x,y-1)){
			cntt+= findPath(x,y-1);
		}
		// x, y+1 Right
		if(isSafe(x,y+1) && isOne(x,y+1)){
			cntt+= findPath(x,y+1);
		}
		// x+1, y Down
		if(isSafe(x+1,y) && isOne(x+1,y)){
			cntt+= findPath(x+1,y);
		}
		// x-1, y Up
		if(isSafe(x-1,y) && isOne(x-1,y)){
			cntt+= findPath(x-1,y);
		}
	}
	return cntt;
}
void father(){
	for(int j=0;j<N;j++){
		for(int i=0;i<N;i++){
			if(vec[i][j]==1 && visited[i][j]==false){
				clusters++;
				vecD[i][j].first=clusters;
				int cnt = findPath(i,j);
				vecD[i][j].second=cnt;
			}
		}
	}
}
int main(){
	init();
	print();
	cout << "\nResult:\n";
	father();
	cout << endl;
	printQQ();
	cout << "\nTotal Ones:";
	cout << ones << endl;
	printQ();

	cout << "\nTotal Clusters:";
	cout << clusters << endl;

	return 0;
}

Post a Comment

Post a Comment (0)

Previous Post Next Post