Untitled

#include <iostream>
using namespace std;

int N;
int map[105][105];
int map1[105][105];
int vis[105][105];
int sl[6]={};
int zero_pos[10100][2];
int N_ze;

int Qx[10000000];
int Qy[10000000];
int top=-1, bot=-1;

int Qx1[10000000];
int Qy1[10000000];
int top1=-1, bot1=-1;

bool is_Empty(){
	return (top==bot);
}

void push(int x, int y){
	top++;
	Qx[top] = x;
	Qy[top] = y;
}

void pop(){
	bot++;
}

void reset(){
	top = bot =-1;
}

//queue 1
bool is_Empty1(){
	return (top1 == bot1);
}

void push1(int x, int y){
	top1++;
	Qx1[top1] = x;
	Qy1[top1] = y;
}

void pop1(){
	bot1++;
}

void reset1(){
	top1 = bot1 =-1;
}

void clear_vis_sl(){
	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j <= N; j++)
		{
			vis[i][j] =0;
		}
		if (i<6)
		{
			sl[i]=0;
		}
	}
}


int max_arr(int arr[]){
	int lnh=0;
	int index;
	for (int i = 1; i < 6; i++)
	{
		if( sl[i] >= lnh)
		{
			lnh = sl[i];
			index = i;
		}
	}
	return index;
}

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void BFS1(int arr[105][105]){

	while (!is_Empty1())
	{
		int r = Qx1[bot1+1];
		int c = Qy1[bot1+1];
		pop1();
		for (int k = 0; k < 4; k++)
		{
			int nextR = r + dx[k];
			int nextC = c + dy[k];
			if (nextR <0 || nextR >=N || nextC <0 || nextC>=N || vis[nextR][nextC] == 1) continue;
			if (arr[nextR][nextC] == arr[r][c])
			{
				int a = arr[nextR][nextC];
				sl[a]++;
				vis[nextR][nextC] =1;
				push1(nextR,nextC); 
			}
		}
	}
}


void BFS0(int x, int y){
	push(x,y);
	vis[x][y] = 1;
	while (!is_Empty())
	{
		int r = Qx[bot+1];
		int c = Qy[bot+1];
		pop();
		for (int k = 0; k < 4; k++)
		{
			int nextR = r + dx[k];
			int nextC = c + dy[k];
			if (nextR <0 || nextR >=N || nextC <0 || nextC>=N || vis[nextR][nextC] == 1) continue;
			if(map[nextR][nextC] ==0){
				vis[nextR][nextC] = 1;
				push(nextR,nextC);
			}
			else
			{
				int a = map[nextR][nextC];
				sl[a]++;
				vis[nextR][nextC] =1;
				push1(nextR,nextC);
			}

		}

	}

}

int main(){
	//freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		cin>>N;

		//reset
		reset();
		reset1();
		clear_vis_sl();
		N_ze = -1;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin>>map[i][j];
				map1[i][j] = map[i][j];
				if (map[i][j] == 0)
				{
					N_ze++;
					zero_pos[N_ze][0]=i;
					zero_pos[N_ze][1]=j;
				}
			}
		}

		for (int i = 0; i <= N_ze ; i++)
		{
			if ( map1[zero_pos[i][0]][zero_pos[i][1]] == 0)
			{
				BFS0(zero_pos[i][0],zero_pos[i][1]);
				BFS1(map);

				int so = max_arr(sl);
				for (int j = 0; j <= N_ze; j++)
				{
					if (vis[zero_pos[j][0]][zero_pos[j][1]] == 1 && map[zero_pos[j][0]][zero_pos[j][1]] == 0)
					{
						map1[zero_pos[j][0]][zero_pos[j][1]] = so;
					}
				}
				clear_vis_sl();
				reset();
				reset1();
			}
		}
		int dem = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (vis[i][j] == 0)
				{
					push1(i,j);
					vis[i][j]=1;
					BFS1(map1);
					dem++;
				}
			}
		}
		cout<<"Case #"<<tc<<endl<<dem<<endl;
	}

	return 0;
}