Untitled
unknown
plain_text
a year ago
4.4 kB
2
Indexable
Never
package hugo_dem_vung; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, res; static int[][] a, visit, vis; static int[] dx = { -1, 0, 1, 0 }, dy = { 0, -1, 0, 1 }; static int[] qx = new int[10000], qy = new int[10000], dientich, ke, quex = new int[10000], quey = new int[10000]; public static boolean checkOut(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) { return false; } return true; } public static void BFS(int x, int y, int v) { int front = 0, rear = 0; qx[front] = x; qy[front] = y; visit[x][y] = 1; while (front <= rear) { int xt = qx[front], yt = qy[front]; for (int i = 0; i < 4; i++) { int nx = xt + dx[i], ny = yt + dy[i]; if (checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] == v) { rear++; qx[rear] = nx; qy[rear] = ny; visit[nx][ny] = 1; } } front++; } } public static int zone() { int count = 0; visit = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (visit[i][j] == 0) { count++; BFS(i, j, a[i][j]); } } } return count; } public static int BFS_DT(int x, int y, int v) { int front = 0, rear = 0; qx[front] = x; qy[front] = y; // vis[x][y] = 1; while (front <= rear) { int xt = qx[front], yt = qy[front]; // System.out.println("dt " + xt + " " + yt +" "+v); for (int i = 0; i < 4; i++) { int nx = xt + dx[i], ny = yt + dy[i]; if (checkOut(nx, ny) && visit[nx][ny] == 0 && visit[nx][ny] != 5 && a[nx][ny] == v) { rear++; qx[rear] = nx; qy[rear] = ny; visit[nx][ny] = 1; } } front++; } return rear + 1; } public static void run() { visit = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 0 && visit[i][j] == 0) {// tim o 0 dientich = new int[6]; int front = 0, rear = 0; quex[rear] = i; quey[rear] = j; rear++; visit[i][j] = 1; // System.out.println("push " + i + " " + j); while (front < rear) { int xt = quex[front], yt = quey[front]; for (int p = 0; p < 4; p++) { int nx = xt + dx[p], ny = yt + dy[p]; if (checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] == 0) { quex[rear] = nx; quey[rear] = ny; rear++; visit[nx][ny] = 1; // System.out.println("push " + nx + " " + ny); } } front++; } front = 0; vis = new int[n][n]; while (front < rear) { int xt = quex[front], yt = quey[front]; for (int p = 0; p < 4; p++) { int nx = xt + dx[p], ny = yt + dy[p]; if (checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] != 0) { visit[nx][ny] = 1; dientich[a[nx][ny]] += BFS_DT(nx, ny, a[nx][ny]); } } front++; } for (int p = 0; p < n; p++) { for (int q = 0; q < n; q++) { if (a[p][q] != 0 && visit[p][q] == 1) { visit[p][q] = 0; } } } int max = 0, value = 0; for (int p = 1; p < 6; p++) { // System.out.print(dientich[p] + " "); if (dientich[p] >= max) { max = dientich[p]; value = p; } } // System.out.println(); // System.out.println("max : " + value); for (int p = 0; p < rear; p++) { // System.out.println(quex[p] + " " + quey[p]); a[quex[p]][quey[p]] = value; visit[quex[p]][quey[p]] = 5; } // System.out.println("----------"); } } } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); a = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = scanner.nextInt(); } } run(); System.out.println("Case #" + t + "\n" + zone()); } scanner.close(); } }