Untitled

#include<iostream>
using namespace std;
int T,N,a[101][101],visited[101][101];
int visited2[101][101]={0};
int res;
int used[101][101]={0};
int used2[101][101]={0};
int dr[4]={0,-1,0,1};
int dc[4]={-1,0,1,0};
int map[101][101];
const int MAX=200000;

struct Queue
{
	int queue[MAX];
	int front;
	int rear;

	Queue(){
		reset();
	}
	void reset(){
		front=-1;
		rear=-1;
	}
	void push(int value){
		queue[++rear]=value;
	}
	int pop(){
		return queue[++front];
	}
	bool isEmpty(){
		return front==rear;
	}
};

void bfs(int x,int y){
	Queue q;
	q.push(x);
	q.push(y);
	visited2[x][y]=1;
	int value=a[x][y];
	while(!q.isEmpty()){
		int r=q.pop();
		int c=q.pop();
		for (int i =0 ;i<4;i++){
			int _r=r+dr[i];
			int _c=c+dc[i];
			if(_r>=0&&_c>=0&&_r<N&&_c<N && a[_r][_c]==value&&!visited2[_r][_c]){
				visited2[_r][_c]=1;
				q.push(_r);
				q.push(_c);
			}
		}
	}
}
void duyet0(int x,int y){
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			visited[i][j]=0;
			used[i][j]=0;
			used2[i][j]=0;
			visited2[i][j]=0;
		}
	}
	Queue q;
	q.push(x);
	q.push(y);
	visited[x][y]=6;
	while(!q.isEmpty()){
		int r=q.pop();
		int c=q.pop();
		for (int i =0 ;i<4;i++){
			int _r=r+dr[i];
			int _c=c+dc[i];
			if(_r>=0&&_c>=0&&_r<N&&_c<N && a[_r][_c]==0&&!visited[_r][_c]){
				visited[_r][_c]=6;
				q.push(_r);
				q.push(_c);
			}
		}
	}
	int counting[101][101]={0};
	int count[101]={0};
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			if(visited[i][j]==6){
				for (int k=0 ;k<4;k++){
					int r=i+dr[k];
					int c=j+dc[k];
					if(r>=0&&c>=0&&r<N&&c<N&& !used[r][c]&&a[r][c]!=0){
						int value=a[r][c];
						counting[r][c]=value;
						count[value]+=1;
						used[r][c]=1;
					}
				}
			}
		}
	}
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			if(counting[i][j]>0){
				int value=counting[i][j];
				/*used2[i][j]=1;
				count[value]++;*/
				for (int k=0 ;k<4;k++){
					int r=i+dr[k];
					int c=j+dc[k];
					if(r>=0&&c>=0&&r<N&&c<N&& !used2[r][c]&&a[r][c]==value){
						used2[r][c]=1;
						count[value]++;
					}
				}
			}
		}
	}
	int max=0;
	int value=0;
	for (int i=1 ;i<=5;i++){
		if(count[i]>=max){
			max=count[i];
			value=i;
		}
	}
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			if(visited[i][j]==6){
				map[i][j]=value;
			}
		}
	}
}
void merge(){
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			if(map[i][j]>0){
				int value=map[i][j];
				a[i][j]=value;
			}
		}
	}
}
void reset(){
	for (int i=0 ;i<N;i++){
		for (int j=0 ;j<N;j++){
			visited[i][j]=0;
			used[i][j]=0;
			used2[i][j]=0;
			visited2[i][j]=0;
			map[i][j]=0;
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	cin>>T;
	for (int t=1; t<=T;t++){
		cin>>N;
		reset();
		for (int i=0 ;i<N;i++){
			for (int j=0 ;j<N;j++){
				cin>>a[i][j];
			}
		}
		for (int i=0 ;i<N;i++){
			for (int j=0 ;j<N;j++){
				//reset();
				if(a[i][j]==0&&!visited[i][j]){
					duyet0(i,j);
				}
			}
		}

		merge();
		res=0;
		for (int i=0 ;i<N;i++){
			for (int j=0 ;j<N;j++){
				visited2[i][j]=0;
			}
		}
		for (int i=0 ;i<N;i++){
			for (int j=0 ;j<N;j++){
				if(!visited2[i][j]){
					bfs(i,j);
					res++;
				}

			}
		}
		cout<<"Case #"<<t<<endl;
		cout<<res<<endl;
	}
	return 0;
}