Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.0 kB
3
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String args[]) throws FileNotFoundException {
		System.setIn(new FileInputStream("C:\\Users\\SVMC\\workspace\\adv\\Test\\src\\input.txt"));
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();
		for(int t=1; t<=T; t++){
			n = sc.nextInt();
			int[][] a = new int[n+5][n+5];
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					a[i][j]=sc.nextInt();
				}
			}
			
			int[][] vis = new int[n+5][n+5];
			int[] f = new int[n+5];
			int[] v_0 = new int[n*n+5];
			int sz_v_0 = 0;
			int vvv = 6;
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(a[i][j]==0 && vis[i][j]==0){
						for(int z=1; z<=5; z++){
							f[z]=0;
						}
						
						solve(i, j, a, vis, f, vvv);
						
						int max=0, idx_max=-1;
						for(int z=1; z<=5; z++){
							if(f[z]>=max){
								max=f[z]; idx_max=z;
							}
						}
						vvv++;
						v_0[sz_v_0++]=idx_max;
					}
				}
			}
			
//			for(int i=0; i<sz_v_0; i++){
//				System.out.println(v_0[i]);
//			}
			
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(a[i][j]>5){
						a[i][j] = v_0[a[i][j]-5-1];
					}
//					System.out.print(a[i][j]+" ");
				}
//				System.out.println();
			}
			
			int res=0;
			int[][] vis3 = new int[n+5][n+5];
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
					if(vis3[i][j]==0){
						BFS(i, j, a, vis3);
						res++;
					}
				}
			}
			
			System.out.println("Case #"+t);
			System.out.println(res);

		}
	}
	
	static void solve(int x, int y, int[][] arr, int[][] vis, int[] f, int vvv){
		int[][] vis2 = new int[n+5][n+5];
		int[][] q = new int[105*105][2];
		int l=0, r=0;
		q[r][0]=x; q[r][1]=y; r++;
		vis[x][y]=1;
		arr[x][y]=vvv;
		while(l<r){
			x = q[l][0];
			y = q[l][1]; l++;
			for(int i=0; i<4; i++){
				int xx=x+dx[i];
				int yy=y+dy[i];
				if(xx>=0 && xx<n && yy>=0 && yy<n && vis[xx][yy]==0){
					if(arr[xx][yy]==0){
						q[r][0]=xx; q[r][1]=yy; r++;
						vis[xx][yy]=1;
						arr[xx][yy]=vvv;
					}else if(arr[xx][yy]!=0 && vis2[xx][yy]==0){
						
						int tmp = BFS(xx, yy, arr, vis2);
//						System.out.println("xet "+arr[xx][yy]+" "+tmp);
						f[arr[xx][yy]] += tmp;
					}
				}
			}
		}
	}
	
	static int BFS(int x, int y, int[][] arr, int[][] vis){
		int cnt = 0;
		int[][] q = new int[105*105][2];
		int l=0, r=0;
		q[r][0]=x; q[r][1]=y; r++;
		vis[x][y]=1;
		while(l<r){
			x = q[l][0];
			y = q[l][1]; l++;
			cnt++;
			for(int i=0; i<4; i++){
				int xx=x+dx[i];
				int yy=y+dy[i];
				if(xx>=0 && xx<n && yy>=0 && yy<n && vis[xx][yy]==0 && arr[xx][yy]==arr[x][y]){
					q[r][0]=xx; q[r][1]=yy; r++;
					vis[xx][yy]=1;
				}
			}
		}
		return cnt;
	}
	
}