# Untitled

unknown
plain_text
20 days ago
2.8 kB
2
Indexable
Never
```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;
}
}```