Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
1
Indexable
Never
#include<iostream>
using namespace std;
#define size 100000
int queue[size];
int front=-1;
int rear =-1;
int N;
int map[105][105];
int map_cp[105][105];
int visit[105][105];
int cntArea[6];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool isEmpty(){
	return front == rear;
}
void push(int x) {
	if( rear == size -1 ) rear =-1;
	rear++;
	queue[rear]=x;
}
int pop(){
	if( front == size -1) front = -1;
	front ++;
	return queue[front];
}
void bfs(int x, int y){
	front = rear =-1;
	push( x) ;
	push( y);
	visit[x][y]=1;
	while (!isEmpty())
	{
		int x1= pop();
		int y1 = pop();

		for( int i=0; i<4; i++){
			int x2= x1+  dx[i];
			int y2 = y1 + dy[i];
			if( x2>=0 && x2<N && y2<N && y2>=0 && visit[x2][y2]==0){
				if( map[x1][y1]==0 || ( map[x2][y2]==map[x1][y1])){
					visit[x2][y2]=1;
					push(x2);
					push(y2);
					cntArea[map[x2][y2]]++;
				}

			}

		}

	}
}
void bfs_vung(int x, int y){
	front =rear=-1;
	push(x);
	push(y);
	visit[x][y]=1;
	while (!isEmpty())
	{
		int x1= pop();
		int y1= pop();
		for(int i=0 ; i< 4; i++){
			int x2= x1+ dx[i];
			int y2 = y1 + dy[i];
			if( x2>=0 && x2<N && y1>=0 && y2<N && visit[x2][y2]==0 && map_cp[x1][y1]==map_cp[x2][y2]){
				visit[x2][y2]=1;
				push( x2);
				push(y2);
			}

		}

	}
}


void reset(){
	for( int i =0 ; i<105; i++){
		for( int j=0 ; j<105; j++){
			visit[i][j]=0;
		}
	}

	for( int i= 0 ; i<6; i++){
		cntArea[i]=0;
	}
}


int main(){
	freopen("text.txt" ,"r ", stdin);
	int t;
	cin>>t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin>>N;
		for( int i=0 ; i<N; i++) {
			for (int j = 0; j < N; j++)
			{
				cin>>map[i][j];
				map_cp[i][j]=map[i][j];
			}
		}
		for( int i =0 ; i< N ; i++){
			for( int j=0 ; j<N; j++){
				if( map_cp[i][j]==0){
					reset();
					bfs( i , j);             // bfs de tim nhung so vung quanh 0
					int lon=-1;
					int he =0;
					for( int ii =1 ; ii< 6 ; ii++){    // tim max lon nhat trong vung
						if( lon<= cntArea[ii]) {
							lon= cntArea[ii];
							he=ii;
						}
					}
					for( int k = 0 ; k<N  ; k++){
						for( int h=0 ; h<N; h++){
							if( visit[k][h]==1 && map[k][h]==0){
								map_cp[k][h]=he;
							}
						}		
					}
				}
			}

		}
		int cnt=0;
		reset();
		for( int i =0 ; i<N; i++){
			for( int j=0 ; j< N; j++){
				if( visit[i][j]==0){
					bfs_vung(i,j);
					cnt++;
				}

			}

		}
		cout<<"Case #"<<tc<<endl;
		cout<<cnt<<endl;
	}
	return 0;
}