Untitled

#include <iostream>
#include <stdio.h>
using namespace std;
int T, n;
int arr[1001][1001], visit[1001][1001];
int dem[6];
int kq, flag;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int ddx[8] = {-1,-1,0,1,1,1,0,-1};
int ddy[8] = {0,1,1,1,0,-1,-1,-1};
int rear, front;
int sl1;

struct toado {
	int x;
	int y;
	int kq;
};
toado queue[10000000];
void init(int t) {
	rear = t;
	front = t;
}
void push(int xx, int yy, int kq) {
	queue[rear].x = xx;
	queue[rear].y = yy;
	queue[rear].kq = kq;
	rear ++;
}
toado pop() {
	toado td = queue[front];
	front ++;
	return td;
}

void BFS(int x, int y) {
	int sl2 = sl1+1;
	init(sl1);
	push(x,y,0);
	visit[x][y] = -1;
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if(xx >= 0 && xx < n && yy >= 0 && yy < n && arr[xx][yy] == 0) {
				push(xx, yy, 0);
				arr[xx][yy] = -1;
				visit[xx][yy] = -1;
				sl2 ++;
			}
		}
	}
	for(int i = sl1; i < sl2; i ++) {
		for(int j = 0; j < 8; j ++) {
			int xx = queue[i].x + ddx[j];
			int yy = queue[i].y + ddy[j];
			if(xx >= 0 && xx < n && yy >= 0 && yy < n && arr[xx][yy] != 0 && arr[xx][yy] != -1 && visit[xx][yy] == 0) {
				int h = arr[xx][yy];
				dem[h] ++;
				visit[xx][yy] = -1;
			}
		}
	}
	int sav = -1, sav2;
	for(int i = 1; i <= 5; i ++) {
		if(dem[i] >= sav) {
			sav = dem[i];
			sav2 = i;
		}
	}
	for(int i = sl1; i < sl2; i ++) queue[i].kq = sav2;
	sl1 = sl2;
}

void set_visit() {
	for(int ii = 0; ii < n; ii++) {
		for(int jj = 0; jj < n; jj ++) {
			visit[ii][jj] = 0;
		}
	}
}

void vung() {
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			if(arr[i][j] == 0) {
				for(int i = 1; i <= 5; i ++) dem[i] = 0;
				arr[i][j] = -1;
				BFS(i,j);
				for(int i = 0; i < n; i ++) {
					for(int j = 0; j < n; j ++) {
						cout << visit[i][j] << " ";
					}
					cout << endl;
				}
				i = 100; j = 100;
				set_visit();
			}
		}
	}
}

void bfs(int x, int y) {
	init(0);
	push(x,y,0);
	visit[x][y] = 1;
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if(xx >= 0 && xx < n && yy >= 0 && yy < n && visit[xx][yy] == 0 && arr[xx][yy] == arr[x][y]) {
				push(xx, yy, 0);
				visit[xx][yy] = 1;
			}
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int stt = 1; stt <= T; stt++) {   
		cin >> n;
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < n; j ++) {
				cin >> arr[i][j];
				visit[i][j] = 0;
			}
		}
		sl1 = 0; kq = 0; 
		vung();
		for(int i = 0; i < sl1; i ++) {
			int x = queue[i].x;
			int y = queue[i].y;
			int c = queue[i].kq;
			arr[x][y] = c;
		}

		//set_visit();

		//for(int i = 0; i < n; i ++) {
		//	for(int j = 0; j < n; j ++) {
		//		if(visit[i][j] == 0) {
		//			bfs(i,j);
		//			kq++;
		//		}
		//	}
		//}

		set_visit();
		//for(int i = 0; i < n; i ++) {
		//	for(int j = 0; j < n; j ++) {
		//		cout << arr[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		cout << "Case #" << stt << endl << kq << endl;
	}
		return 0;
}