Untitled

#include <iostream>
using namespace std;
#define MAX 105
#define INF 0
int map[MAX][MAX] = { 0 }, visited[MAX][MAX] = { 0 };
int visitAppend[MAX][MAX] = { 0 };
int n; int ans = INF; int arr[6] = { 0 }; int size = 0;
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

void resetArr(){
	for(int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			visited[i][j] = 0;
		}
	}
}

struct Point{
	int x, y, step;
};

struct Queue{
	Point *data;
	int front, rear, maxSize;
	Queue(int maxSize){
		this->maxSize = maxSize;
		data = new Point[this->maxSize];
		front = -1; rear = -1;
	}
	~Queue() { delete[] data; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return rear == maxSize; }
	void enQueue(Point p) { if(!isFull()) data[++rear] = p; }
	Point deQueue() { if(!isEmpty()) return data[++front]; }
	void resetQueue() { front = rear = -1; }
};

Queue q(MAX*MAX);
void BFS(int i, int j){
	Point start = { i, j, 0}; visited[i][j] = 1; visitAppend[i][j] = 1;
	q.enQueue(start);

	int x, y, step;
	while (!q.isEmpty()){
		Point currentP; currentP = q.deQueue();
		x = currentP.x; y = currentP.y; step = currentP.step;

		for (int l = 0; l < 4; l++){
			int nx = x + dx[l];
			int ny = y + dy[l];

			if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if(map[nx][ny] != 0 || visited[nx][ny] == 1) continue;

			visited[nx][ny] = 1;
			visitAppend[nx][ny] = 1;
			Point next = { nx, ny, step+1 };
			q.enQueue(next);
		}
	}

	size = q.rear;
	q.front = -1;

	for (int idx = 5; idx >= 1; idx--){
		while (!q.isEmpty())
		{
			Point currentP; currentP = q.deQueue();
			x = currentP.x; y = currentP.y; step = currentP.step;
			for (int l = 0; l < 4; l++){
				int nx = x + dx[l];
				int ny = y + dy[l];

				if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] == 1 || visitAppend[nx][ny] == 1) continue;
				if(map[nx][ny] == idx) {
					visited[nx][ny] = 1;
					Point next = { nx, ny, step+1 };
					q.enQueue(next);
					arr[idx]++;
				}
			}
		}
		q.resetQueue();
		q.rear = size;
	}

	int indexMax = -1; int temp = -1;
	for(int idx = 5; idx >= 1; idx--) { if(arr[idx] > temp) { indexMax = idx; temp = arr[idx]; } }
	while (!q.isEmpty()){
			Point currentP; currentP = q.deQueue();
			x = currentP.x; y = currentP.y; step = currentP.step;
			map[x][y] = indexMax;
	} 

	for(int k = 1; k <= 5; k++) arr[k] = 0;
}

void countZone(int i, int j, int number){
	Point start = { i, j, 0}; visited[i][j] = 1;
	q.enQueue(start);

	int x, y, step;
	while (!q.isEmpty())
	{
		Point currentP; currentP = q.deQueue();
		x = currentP.x; y = currentP.y; step = currentP.step;
		for (int l = 0; l < 4; l++){
			int nx = x + dx[l];
			int ny = y + dy[l];

			if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] == 1) continue;
			if(map[nx][ny] == number) {
				visited[nx][ny] = 1;
				Point next = { nx, ny, step+1 };
				q.enQueue(next);
			}
		}
	}
}

void reset(){
	for(int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			visited[i][j] = 0;
			visitAppend[i][j] = 0;
		}
	}
}

int main(){
	//freopen("thong_tri.txt", "r", stdin);
	int T;	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> n;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				cin >> map[i][j];
			}
		}

		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if(map[i][j] == 0){ 
					BFS(i, j); 
					resetArr(); q.resetQueue(); 
				}
			}
		}

		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if(visited[i][j] == 0){ 
					countZone(i, j, map[i][j]);
					ans++;
					q.resetQueue(); 
				}
			}
		}

		//
		cout << "Case #" << tc + 1 << "\n" << ans << endl;
		ans = INF; reset();

	} return 0;
}