Untitled

Case #1 11 / Case #2 1 / Case #3 31 / Case #4 130 / Case #5 60 / Case #6 44 / Case #7 51 / Case #8 51 / Case #9 47 / Case #10 1231 / Case #11 1205 / Case #12 1224 / Case #13 1226 / Case #14 1204 / Case #15 1234 / Case #16 1256 / Case #17 1207 / Case #18 1227 / Case #19 1201 / Case #20 1199 / Case #21 1176 / Case #22 1205 / Case #23 1218 / Case #24 1215 / Case #25 1207 / Case #26 1180 / Case #27 1159 / Case #28 1175 / Case #29 1177 / Case #30 3129 / Case #31 4849 / Case #32 4740 / Case #33 4721 / Case #34 4713 / Case #35 4838 / Case #36 4792 / Case #37 4675 / Case #38 4702 / Case #39 4778 / Case #40 4833 / Case #41 4774 / Case #42 4778 / Case #43 4785 / Case #44 4828 / Case #45 4764 / Case #46 4776 / Case #47 4763 / Case #48 4724 / Case #49 4836 / Case #50 4723

public class Solution {
	static int N, count;
	static int id;
	static Queue<Point> q;
	static int[] sum = new int[6];
	static int[] z = new int[100000];
	static boolean[][] s;
	static boolean[][] v;
	static int[][] m;
	static int[] a = new int[10000];
	static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			m = new int[N][N];
			v = new boolean[N][N];
			s = new boolean[N][N];
			q = new Queue<Point>();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					m[i][j] = sc.nextInt();
				}
			}
			solve();
			System.out.println("Case #" + tc);
			System.out.println(count);
		}
	}

	static void solve() throws Exception {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (m[i][j] == 0) {
					int sx = i;
					int sy = j;
					for (int k = 1; k <= 5; k++) {
						sum[k] = 0;
					}
					id = 0;
					z[id++] = sx;
					z[id++] = sy;
					q.reset();
					q.enQueue(new Point(sx, sy));
					v = new boolean[N][N];
					Point p;
					while (!q.isEmpty()) {
						p = q.peek();
						q.deQueue();
						for (int d = 0; d < 4; d++) {
							int nx = p.x + dx[d];
							int ny = p.y + dy[d];
							if (isValid(nx, ny) && !v[nx][ny] && !s[nx][ny]) {
								if (m[p.x][p.y] == 0) {
									v[nx][ny] = true;
									if (m[nx][ny] == 0) {
										z[id++] = nx;
										z[id++] = ny;
									}
									q.enQueue(new Point(nx, ny));
									sum[m[nx][ny]]++;
								} else if (m[p.x][p.y] == m[nx][ny]) {
									v[nx][ny] = true;
									q.enQueue(new Point(nx, ny));
									sum[m[nx][ny]]++;
								}

							}
						}
					}

					int index = 1;
					for (int k = 2; k <= 5; k++) {
						if (sum[index] <= sum[k]) {
							index = k;
						}
					}
					int k = 0;
					while (k < id) {
						int x = z[k++];
						int y = z[k++];
						m[x][y] = index;
						s[x][y] = true;
					}
				}
			}
		}

		v = new boolean[N][N];
		count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!v[i][j]) {
					count++;
					q.reset();
					q.enQueue(new Point(i, j));
					Point pt;
					while (!q.isEmpty()) {
						pt = q.peek();
						q.deQueue();
						for (int d = 0; d < dx.length; d++) {
							int nx = pt.x + dx[d];
							int ny = pt.y + dy[d];
							if (isValid(nx, ny) && !v[nx][ny] && m[pt.x][pt.y] == m[nx][ny]) {
								v[nx][ny] = true;
								q.enQueue(new Point(nx, ny));
							}
						}
					}
				}
			}
		}
	}
	
	static boolean isValid(int x, int y) {
		if (x >= 0 && y >= 0 && x < N && y < N) {
			return true;
		}
		return false;
	}
}