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