Untitled

#include <iostream>
#define MAX_Q 40000
using namespace std;

int board[105][105];
int saveboad[105][105];
int mark[105][105];
int tmpboard[105][105];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int N,ans;


typedef struct {
	int x;
	int y;
} Node;

class Queue {
	private: int front;
	int rear;
	Node arr[MAX_Q];
	public: Queue() {
		front = -1;
		rear = -1;
	}
	bool isFull() {
		return (rear == MAX_Q - 1);
	}
	int size(){
		return rear;
	}
	bool isEmpty() {
		return (front == -1 && rear == -1);
	}
	void enqueue(Node x) {
		if (isFull()) {
			return;
		}
		if (isEmpty()) {
			front = 0;
			rear = 0;
		} else {
			rear++;
		}
		arr[rear] = x;
	}
	void dequeue() {
		if (isEmpty()) {
			return;
		}
		if (front == rear) {
			front = -1;
			rear = -1;
		} else {
			front++;
		}
	}
	Node peek() {
		if (isEmpty()) {
			return Node();
		}
		return arr[front];
	}
};



void bfs(Node a){

	Queue q;
	int sum[6] = {0,0,0,0,0,0};
	q.enqueue(a);
	Node save0[MAX_Q];
	mark[a.x][a.y] = true;
	int k = 0;
	while (!q.isEmpty())
	{
		Node oldNode = q.peek();
		q.dequeue();
		if (board[oldNode.x][oldNode.y] == 0)
		{
			k++;
			save0[k] = oldNode;
		}
		if (board[oldNode.x][oldNode.y] == 0)
		{
			for (int i = 0; i < 4; i++)
			{
				Node nextNode;
				nextNode.x = oldNode.x + dx[i];
				nextNode.y = oldNode.y + dy[i];
				if (nextNode.x > N || nextNode.x <1 ) continue;
				if (nextNode.y > N || nextNode.y <1 ) continue;
				if (!mark[nextNode.x][nextNode.y])
				{
					mark[nextNode.x][nextNode.y] = true;
					sum[board[nextNode.x][nextNode.y]]++;
					q.enqueue(nextNode);
				}
			}
		}
		if (board[oldNode.x][oldNode.y] != 0 )
		{
			for (int i = 0; i < 4; i++)
			{
				Node nextNode;
				nextNode.x = oldNode.x + dx[i];
				nextNode.y = oldNode.y + dy[i];
				if (nextNode.x > N || nextNode.x < 1 ) continue;
				if (nextNode.y > N || nextNode.y < 1 ) continue;
				if (!mark[nextNode.x][nextNode.y] && board[nextNode.x][nextNode.y] == board[oldNode.x][oldNode.y])
				{
					mark[nextNode.x][nextNode.y] = true;
					sum[board[nextNode.x][nextNode.y]]++;
					q.enqueue(nextNode);
				}
			}
		}
	}
	int maxsum = 0;
	int t;
	for (int i = 5; i > 0; i--)
	{
		if (sum[i] > maxsum)
		{
			maxsum = sum[i];
			t = i;
		}
	}
	for (int i = 1; i <= k; i++)
	{
		saveboad[save0[i].x][save0[i].y] = t;
	}
}

void bfsvung(Node dau){
	Queue q;
	q.enqueue(dau);
	mark[dau.x][dau.y]=1;
	
	while (!q.isEmpty()) {
			Node oldNode = q.peek();
			q.dequeue();
			for (int i=0; i<4; i++){
				Node nextNode;
				nextNode.x=oldNode.x+dx[i];
				nextNode.y=oldNode.y+dy[i];
				if (nextNode.x > N || nextNode.x <1 ) continue;
				if (nextNode.y > N || nextNode.y <1 ) continue;
				if (mark[nextNode.x][nextNode.y]==0 && saveboad[nextNode.x][nextNode.y]==saveboad[oldNode.x][oldNode.y]){
					mark[nextNode.x][nextNode.y]=1;
					q.enqueue(nextNode);
				}
			}
	}
};
void initvisit(){
	for (int i=1; i<=N; i++){
		for (int j=1; j<=N; j++){
			mark[i][j]=0;
		}
	}
}
int main(){
	int T;
	//freopen("input.txt","r",stdin);
	cin >>T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >>N;
		for (int i=1; i<=N; i++){
			for (int j=1; j<=N; j++){
				cin >> board[i][j];
				mark[i][j]=0;
				saveboad[i][j]=board[i][j];
			}
		}
		for (int i=1; i<=N; i++){
			for (int j=1; j<=N; j++){
				if (saveboad[i][j]==0){
					Node p;
					p.x=i;
					p.y=j;
					bfs(p);
					initvisit();
				}
			}
		}
		
		ans=0;
		for (int i=1; i<=N; i++){
			for (int j=1; j<=N; j++){
				if (mark[i][j]==0){
					ans++;
					Node pdau;
					pdau.x=i;
					pdau.y=j;
					bfsvung(pdau);
				}
			}
		}
		cout <<"Case #"<< tc + 1 << endl << ans << endl;
	}
	return 0;
}