Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
5.5 kB
1
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int n;
	static int[][] a;
	static int[][] visit;
	static int[] d1 = {-1,1,0,0};
	static int[] d2 = {0,0,-1,1};
	static int[][] tham;
	static int[] tansuat;
	static int[][] b;
	static int[] vung;
	
	public static void main(String[] args)  {
		//System.setIn(new FileInputStream("src/Hugo_Dem_Vung/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			a = new int[n][n];
			b = new int[n][n];
			visit = new int[n][n];
			tham = new int[n][n];
			tansuat = new int[n+1];
			vung = new int[n*n];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					a[i][j] = sc.nextInt();
					b[i][j] = a[i][j];
				}
			}
			
			int dem1 = 6;
			for(int u = 0; u < n; u++){
				for(int v = 0; v < n; v++){
					if(a[u][v] == 0 && visit[u][v] == 0){
						bfs(u,v, dem1);
						int max = -1;
						int td = -1;
						for(int i = 1; i <= n; i++){
							if(max <= tansuat[i]){
								max = tansuat[i];
								td = i;
							}
						}
						update1();
						vung[dem1] = td;
						dem1++;
						//bfsUpdate(u, v, td);
						
						/*for(int i = 0; i < n; i++){
							for(int j = 0; j < n; j++){
								System.out.print(b[i][j] + " ");
							}
							System.out.println();
						}
						System.out.println();*/
					}
				}
			}
			
			//System.out.println(dem1-6);
			
			for(int u = 0; u < n; u++){
				for(int v = 0; v < n; v++){
					if(b[u][v] > 5){
						for(int z = 6; z < dem1; z++){
							if(b[u][v] == z){
								b[u][v] = vung[z];
							}
						}
					}
				}
			}
			
			/*for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					System.out.print(b[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();*/
			
			update();
			
			int dem = 0;
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					if(visit[i][j] == 0){
						int m = b[i][j];
						bfsDem(i,j,m);
						//System.out.println(i + " " + j);
						dem++;
						
						/*for(int i1 = 0; i1 < n; i1++){
							for(int j1 = 0; j1 < n; j1++){
								System.out.print(visit[i1][j1] + " ");
							}
							System.out.println();
						}*/
					}
				}
			}
			
			/*for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					System.out.print(b[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();*/
			
			
			System.out.println("Case #" + test_case);
			System.out.println(dem);
		}	
	}
	
	public static void update1(){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				tham[i][j] = 0;
			}
		}
		
		for(int i = 1; i <= n; i++){
			tansuat[i] = 0;
		}
	}
	
	public static void update(){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				tham[i][j] = 0;
				visit[i][j] = 0;
			}
		}
		
		for(int i = 1; i <= n; i++){
			tansuat[i] = 0;
		}
	}
	
	public static void bfsDem(int u, int v, int k){
		int[] q = new int[100*100+5];
		int[] w = new int[100*100+5];
		int l = 0, r = 0;
		visit[u][v] = 1;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l];
			int y = w[l]; l++;
			for(int i = 0; i < 4; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				if(xx>=0 && yy>=0 && xx<n && yy<n){
					if(visit[xx][yy] == 0){
						if(b[xx][yy] == k){
							visit[xx][yy] = 1;
							q[r] = xx;
							w[r] = yy;
							r++;
						}
					}
				}
			}
		}
	}
	
	public static void bfsUpdate(int u, int v, int k){
		int[] q = new int[100*100+5];
		int[] w = new int[100*100+5];
		int l = 0, r = 0;
		visit[u][v] = 1;
		b[u][v] = k;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l];
			int y = w[l]; l++;
			for(int i = 0; i < 4; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				if(xx>=0 && yy>=0 && xx<n && yy<n){
					if(visit[xx][yy] == 0){
						if(a[xx][yy] == 0){
							visit[xx][yy] = 1;
							b[xx][yy] = k;
							q[r] = xx;
							w[r] = yy;
							r++;
						}
					}
				}
			}
		}
	}
	
	public static void bfs(int u, int v, int dem1){
		int[] q = new int[100*100+5];
		int[] w = new int[100*100+5];
		int l = 0, r = 0;
		visit[u][v] = 1;
		b[u][v] = dem1;
		q[r] = u;
		w[r] = v;
		r++;
		while(l < r){
			int x = q[l];
			int y = w[l]; l++;
			for(int i = 0; i < 4; i++){
				int xx = x+d1[i];
				int yy = y+d2[i];
				if(xx>=0 && yy>=0 && xx<n && yy<n){
					if(visit[xx][yy] == 0){
						if(a[xx][yy] == 0){
							visit[xx][yy] = 1;
							b[xx][yy] = dem1;
							q[r] = xx;
							w[r] = yy;
							r++;
						}else if(a[xx][yy] != 0){
							int m = a[xx][yy];
							int[] q1 = new int[100*100+5];
							int[] w1 = new int[100*100+5];
							int l1 = 0, r1 = 0;
							if(tham[xx][yy] == 0){
								tansuat[m]++;
							}
							tham[xx][yy] = 1;
							q1[r1] = xx;
							w1[r1] = yy;
							r1++;
							
							while(l1 < r1){
								int x1 = q1[l1];
								int y1 = w1[l1]; l1++;
								for(int i1 = 0; i1 < 4; i1++){
									int xxx = x1+d1[i1];
									int yyy = y1+d2[i1];
									if(xxx>=0 && yyy>=0 && xxx<n && yyy<n){
										if(tham[xxx][yyy] == 0 && a[xxx][yyy] == m){
											tansuat[m]++;
											tham[xxx][yyy] = 1;
											q1[r1] = xxx;
											w1[r1] = yyy;
											r1++;
										}
									}
								}
							}
						}
						
						
					}
				}
			}
		}
	}
}