Untitled
unknown
plain_text
a year ago
2.8 kB
8
Indexable
public class Solution { static int N, count; static int id; static Queue<Point> q; static int[] sum = new int[6]; static int[] z = new int[100000]; static boolean[][] s; static boolean[][] v; static int[][] m; static int[] a = new int[10000]; static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 }; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); m = new int[N][N]; v = new boolean[N][N]; s = new boolean[N][N]; q = new Queue<Point>(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { m[i][j] = sc.nextInt(); } } solve(); System.out.println("Case #" + tc); System.out.println(count); } } static void solve() throws Exception { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (m[i][j] == 0) { int sx = i; int sy = j; for (int k = 1; k <= 5; k++) { sum[k] = 0; } id = 0; z[id++] = sx; z[id++] = sy; q.reset(); q.enQueue(new Point(sx, sy)); v = new boolean[N][N]; Point p; while (!q.isEmpty()) { p = q.peek(); q.deQueue(); for (int d = 0; d < 4; d++) { int nx = p.x + dx[d]; int ny = p.y + dy[d]; if (isValid(nx, ny) && !v[nx][ny] && !s[nx][ny]) { if (m[p.x][p.y] == 0) { v[nx][ny] = true; if (m[nx][ny] == 0) { z[id++] = nx; z[id++] = ny; } q.enQueue(new Point(nx, ny)); sum[m[nx][ny]]++; } else if (m[p.x][p.y] == m[nx][ny]) { v[nx][ny] = true; q.enQueue(new Point(nx, ny)); sum[m[nx][ny]]++; } } } } int index = 1; for (int k = 2; k <= 5; k++) { if (sum[index] <= sum[k]) { index = k; } } int k = 0; while (k < id) { int x = z[k++]; int y = z[k++]; m[x][y] = index; s[x][y] = true; } } } } v = new boolean[N][N]; count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!v[i][j]) { count++; q.reset(); q.enQueue(new Point(i, j)); Point pt; while (!q.isEmpty()) { pt = q.peek(); q.deQueue(); for (int d = 0; d < dx.length; d++) { int nx = pt.x + dx[d]; int ny = pt.y + dy[d]; if (isValid(nx, ny) && !v[nx][ny] && m[pt.x][pt.y] == m[nx][ny]) { v[nx][ny] = true; q.enQueue(new Point(nx, ny)); } } } } } } } static boolean isValid(int x, int y) { if (x >= 0 && y >= 0 && x < N && y < N) { return true; } return false; } }
Editor is loading...
Leave a Comment