Untitled

#include<iostream>
using namespace std;
int a[101][101];
int map[101][101];
int vs[101][101];
int vs1[101][101];
int dem[101];
int n;int t;
int r=-1;int f=-1;
int r1=-1;int f1=-1;
int qx[100000];
int qy[100000];
int qx1[100000];
int qy1[100000];
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
void push1(int x, int y)
{
	r1++;
	qx1[r1]=x;
	qy1[r1]=y;
}
void pop1(int &x, int &y)
{
	f1++;
	x=qx1[f1];
	y=qy1[f1];
}

void push(int x, int y)
{
	r++;
	qx[r]=x;
	qy[r]=y;
}
void pop(int &x, int &y)
{
	f++;
	x=qx[f];
	y=qy[f];
}
bool checkb(int x, int y)
{
	if(x<0||y<0||x>=n||y>=n) return false;
	return true;
}

void bfs1(int x,int y)
{
	push1(x,y);
	while(r1!=f1){
		pop1(x,y);
		for(int i=0; i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(checkb(xx,yy) && a[xx][yy]==a[x][y] && vs[xx][yy]==0){
				vs[xx][yy]=vs[x][y]+1;
				push1(xx,yy);
			}
		}
	}
}
void bfs(int x, int y)
{
	push(x,y);
	vs1[x][y]=1;
	vs[x][y]=1;
	while(r!=f){
		pop(x,y);
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(checkb(xx,yy)){
				if(a[xx][yy]==0 && vs[xx][yy]==0){
				vs[xx][yy]=1;
				vs1[xx][yy]=1;
				push(xx,yy);
				}
				if(a[xx][yy]!=0 && vs[xx][yy]==0){
				vs[xx][yy]=1;
				bfs1(xx,yy);
				}
			}
		}
	}

	int ans1=0;int doi=0;
	for(int i=1;i<=n;i++){
		int tong=0;
		for(int i1=0;i1<n;i1++){
			for(int j=0;j<n;j++){
				if(a[i1][j]==i && vs[i1][j]!=0)
					tong++;
			}
		}//cout<<tong<<endl;
		if(tong>=ans1){
			ans1=tong;
			doi=i;//cout<<ans1<<i<<endl;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(vs[i][j]!=0 && a[i][j]!=0) map[i][j]=a[i][j];
			if(vs[i][j]!=0 && a[i][j]==0) map[i][j]=doi;
			//cout<<map[i][j];
		}//cout<<endl;
	}
}

void tinhvung(int x, int y)
{
	push(x,y);
	vs[x][y]=1;
	while(r!=f){
		pop(x,y);
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(checkb(xx,yy)){
				if(map[xx][yy]==map[x][y] && vs[xx][yy]==0){
					vs[xx][yy]=1;//cout<<xx<<yy<<endl;
					push(xx,yy);
				}
			}
		}
	}
}
int main()
{
	//freopen("input.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 >>a[i][j];
				vs[i][j]=0;
				vs1[i][j]=0;
				map[i][j]=a[i][j];
			}
		}
		r=f=-1;
		r1=f1=-1;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(a[i][j]==0 && vs1[i][j]==0){
					bfs(i,j);
					for(int ii=0;ii<n;ii++)
						for(int jj=0;jj<n;jj++)vs[ii][jj]=0;
				}
			}
		}
		//bfs(2,4);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				vs[i][j]=0;
			}
		}
		int ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(vs[i][j]==0){
					ans++;
					tinhvung(i,j);
				}
			}
		}
		cout<<"Case #"<<tc<<endl<<ans<<endl;
	}
	return 0;
}