Untitled

#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int front = -1;
int rear = -1;
int Arx[MAX_SIZE];
int Ary[MAX_SIZE];

class queue {
public:
	bool isEmpty();
	void push(int arx, int ary);
	void pop();
	void peek(int &arx, int &ary);
};

bool queue :: isEmpty()
{
	if(front == rear)
	{
		return true;
	}
	return false;
}

void queue :: push(int arx, int ary)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
}

void queue :: pop()
{
	rear++;
}

void queue :: peek(int &arx, int &ary)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
}

int front1 = -1;
int rear1 = -1;
int Arx1[MAX_SIZE];
int Ary1[MAX_SIZE];

class queue1 {
public:
	bool isEmpty();
	void push(int arx, int ary);
	void pop();
	void peek(int &arx, int &ary);
};

bool queue1 :: isEmpty()
{
	if(front1 == rear1)
	{
		return true;
	}
	return false;
}

void queue1 :: push(int arx, int ary)
{
	front1++;
	Arx1[front1] = arx;
	Ary1[front1] = ary;
}

void queue1 :: pop()
{
	rear1++;
}

void queue1 :: peek(int &arx, int &ary)
{
	arx = Arx1[rear1 + 1];
	ary = Ary1[rear1 + 1];
}


int N;
int arr[101][101];
int vs[101][101];
int visited[101][101];
int cnt[6];
int vtx[10001];
int vty[10001];
int id = 0;

void reset(int ar[101][101])
{
	for(int i = 0; i < 101; i++)
	{
		for(int j = 0; j < 101; j++)
		{
			ar[i][j] = 0;
		}
	}
	for(int i = 0; i < 6; i++)
	{
		cnt[i] = 0;
	}
	for(int i = 0; i < 10001; i++)
	{
		vtx[i] = 0;
		vty[i] = 0;
	}
	id = 0;
}

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

void BFS1(queue1 qe1)
{
	while(!qe1.isEmpty())
	{
		int x, y;
		qe1.peek(x, y);
		qe1.pop();
		cnt[arr[x][y]]++;
		for(int i = 0; i < 4; i++)
		{
			int t = x + dx[i];
			int k = y + dy[i];
			if(t >= 0 && t < N && k >= 0 && k < N)
			{
				if(vs[t][k] == 0 && arr[t][k] == arr[x][y])
				{
					qe1.push(t, k);
					vs[t][k] = 1;
				}
			}
		}
	}
}

// BFS nhung phan tu 0 va xem nhung phan tu ke no
void BFS(int x1, int y1)
{
	queue qe;
	queue1 qe1;
	front1 = rear1 = -1;
	front = rear = -1;
	reset(vs);
	vs[x1][y1] = 1;
	qe.push(x1, y1);
	while (!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y);
		qe.pop();
		if(arr[x][y] == 0)
		{
			vtx[id] = x;
			vty[id] = y;
			id++;
			for(int i = 0; i < 4; i++)
			{
				int t = x + dx[i];
				int k = y + dy[i];
				if(t >= 0 && t < N && k >= 0 && k < N)
				{
					if(vs[t][k] == 0)
					{
						qe.push(t, k);
						vs[t][k] = 1;
					}
				}
			}
		}
		else
		{
			qe1.push(x, y);
		}
	}
	BFS1(qe1);
	int max = 0;
	int ii = 0;
	for(int i = 5; i >= 1; i--)
	{
		if(max < cnt[i])
		{
			max = cnt[i];
			ii = i;
		}
	}
	for(int i = 0; i < id; i++)
	{
		visited[vtx[i]][vty[i]] = ii;
	}
}


void BFS2(int x1, int y1, int k1)
{
	queue qe;
	qe.push(x1, y1);
	vs[x1][y1] = 1;
	while(!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y);
		qe.pop();
		for(int i = 0; i < 4; i++)
		{
			int t = x + dx[i];
			int k = y + dy[i];
			if(t >= 0 && t < N && k >= 0 && k < N)
			{
				if(arr[t][k] == k1 && vs[t][k] == 0)
				{
					qe.push(t , k);
					vs[t][k] = 1;
				}
			}
		}
	}
}

int main()
{
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		cin >> N;
		reset(arr);
		reset(visited);
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
			}
		}
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				if(arr[i][j] == 0 && visited[i][j] == 0)
				{
					BFS(i, j);
				}
			}
		}

		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				if(visited[i][j] != 0)
				{
					arr[i][j] = visited[i][j];
				}
			}
		}
		int ctt = 0;
		reset(vs);
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				if(vs[i][j] == 0)
				{
					BFS2(i, j, arr[i][j]);
					ctt++;
				}
			}
		}
		cout<<"Case #"<<tc<<endl<<ctt<<endl;
	}
}