Untitled

// Thong Tri Khu Vuc
package ThongTriKhuVuc;

import java.util.Scanner;
class MyQueue{
	private int size;
	private int[] array;
	private int in;
	private int out;
	public MyQueue(int size) {
		this.size = size;
		array=new int[size];
		in=-1;
		out=-1;
	}
	public void push(int x) {
		in++;
		array[in]=x;
	}
	public int pop() {
		out++;
		return array[out];
	}
	public boolean isEmpty() {
		if(in==out) {
			return true;
		}
		return false;
	}
	public void reset() {
		in=out=-1;
	}
	
}
public class test {
static int N;
static int[][] map=new int[100][100];
static int[][] vs=new int[100][100];
static int[] soLan=new int[6];
static MyQueue queueX=new MyQueue(10000);
static MyQueue queueY=new MyQueue(10000);
static MyQueue queueX1=new MyQueue(10000);
static MyQueue queueY1=new MyQueue(10000);
static int[] dx= {0,-1,0,1};
static int[] dy= {-1,0,1,0};
static int count=0;
//reset solan
static void RSsolan() {
	for(int i=0;i<=5;i++) {
		soLan[i]=0;
	}
}
//reset visit
static void RSvisit() {
	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			vs[i][j]=0;
		}
	}
}
//BFS
static void BFS_0(int x,int y) {
	queueX.reset();
	queueY.reset();
	queueX.push(x);
	queueY.push(y);
	vs[x][y]=count;
	while(!queueX.isEmpty()) {
		int xx=queueX.pop();
		int yy=queueY.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==0 && vs[r][c]==0) {
				queueX.push(r);
				queueY.push(c);
				vs[r][c]=count;
			}
			else if(map[r][c]!=0 && vs[r][c]==0) {
				soLan[map[r][c]]++;
				BFS_1(r,c);
			}
		}
	}
}
//BFS_vung
static void BFS_1(int x,int y) {
	queueX1.reset();
	queueY1.reset();
	queueX1.push(x);
	queueY1.push(y);
	vs[x][y]=1;
	while(!queueX1.isEmpty()) {
		int xx=queueX1.pop();
		int yy=queueY1.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==map[xx][yy]&& vs[r][c]==0) {
				queueX1.push(r);
				queueY1.push(c);
				vs[r][c]=1;
				soLan[map[r][c]]++;
			}
		}
	}
}
//BFS Gan
static void BFS_Gan(int x,int y,int val) {
	queueX1.reset();
	queueY1.reset();
	queueX1.push(x);
	queueY1.push(y);
	map[x][y]=val;
	while(!queueX1.isEmpty()) {
		int xx=queueX1.pop();
		int yy=queueY1.pop();
		for(int i=0;i<4;i++) {
			int r=xx+dx[i];
			int c=yy+dy[i];
			if(r<0 || r>=N || c<0 || c>=N ) continue;
			if(map[r][c]==0 && vs[r][c]==count) {
				queueX1.push(r);
				queueY1.push(c);
				map[r][c]=val;
			}
		}
	}
}
//main
public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int T=sc.nextInt();
	for(int tc=0;tc<T;tc++) {
		N=sc.nextInt();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j]=sc.nextInt();
			}
		}
		RSvisit();
		count=2;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]==0 && vs[i][j]==0) {
					RSsolan();
					BFS_0(i, j);
					for(int m=0;m<N;m++) {
						for(int n=0;n<N;n++) {
							if(map[m][n]!=0 && vs[m][n]==1) {
								vs[m][n]=0;
							}
						}
					}
					int max=0;
					int tmp=0;
					for(int m=0;m<=5;m++) {
						if(soLan[m]>=max) {
							max=soLan[m];
							tmp=m;
						}
					}
					BFS_Gan(i, j, tmp);
					count++;
				}
			}
		}
		RSvisit();
		int ans=0;
		for(int m=0;m<N;m++) {
			for(int n=0;n<N;n++) {
				if(vs[m][n]==0) {
					ans++;
					BFS_1(m, n);
				}
			}
		}
		System.out.println("Case #"+(tc+1));
		System.out.println(ans);
	}
}
}



//Sky force
package SkyForce;

import java.util.Scanner;

public class test {
static int N;
static int[][] map=new int[100][5];
static int[][] vs=new int[100][5];
static int ans=0;
static int[] dy= {-1,0,1};
static void reset() {
	for(int i=0;i<N;i++) {
		for(int j=0;j<5;j++) {
			vs[i][j]=0;
		}
	}
}
static void backtrack(int r,int c,int sum,int sobom) {
	if(r==0 && c>=0 && c<5) {
		if(sum>ans) {
			ans=sum;
		}
		return;
	}
	if(sum<0) {
		return;
	}
	for(int i=0;i<2;i++) {
		if(i==0) {
			for(int j=0;j<3;j++) {
				c=c+dy[j];
				if(r-1>=0 && c>=0 && c<5 && map[r-1][c]!=2) {
					backtrack(r-1, c, sum+map[r-1][c], sobom);
				}
				else if(r-1>=0 && c>=0 && c<5 && map[r-1][c]==2){
					backtrack(r-1, c, sum-1, sobom);
				}
				c=c-dy[j];
			}
		}
		else if(i==1 && sobom>0) {
			if(r<5) {
				for(int j=0;j<r;j++) {
					for(int k=0;k<5;k++) {
						if(map[j][k]==2) {
							map[j][k]=0;
							vs[j][k]=1;
						}
					}
				}
			}
			else {
				for(int j=r;j>=r-5;j--) {
					for(int k=0;k<5;k++) {
						if(map[j][k]==2) {
							map[j][k]=0;
							vs[j][k]=1;
						}
					}
				}
			}
			for(int j=0;j<3;j++) {
				c=c+dy[j];
				if(r-1>=0 && c>=0 && c<5 && map[r-1][c]!=2) {
					backtrack(r-1, c, sum+map[r-1][c], sobom-1);
				}
				else if(r-1>=0 && c>=0 && c<5 && map[r-1][c]==2){
					backtrack(r-1, c, sum-1, sobom-1);
				}
				c=c-dy[j];
			}
			for(int j=0;j<N;j++) {
				for(int k=0;k<5;k++) {
					if(vs[j][k]==1) {
						map[j][k]=2;
						vs[j][k]=0;
					}
				}
			}
		}
	}
}

public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int tc=sc.nextInt();
	for(int i=0;i<tc;i++) {
		N=sc.nextInt();
		for(int j=0;j<N;j++) {
			for(int k=0;k<5;k++) {
				map[j][k]=sc.nextInt();
			}
		}
		reset();
		ans=-1;
		backtrack(N,2,0,1);
		System.out.println("Case #"+(i+1));
		System.out.println(ans);
	}
}
}