Untitled
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; } }