Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.1 kB
1
Indexable
Never
package bla;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
class Queue {
	private int maxSize;
	private int [] Array;
	private int front , rear;
	
	public Queue(int s){
		maxSize = s;
		Array = new int[maxSize];
		front = -1;
		rear = -1;
	}
	
	public boolean isEmpty(){
		if(this.front == this.rear){
			return true;
		}
		return false;
	}
	public boolean isFull(){
		if(this.rear == this.maxSize-1){
			return true;
		}
		return false;
	}
	public void Push (int x){
		Array[++rear] = x;
	}
	public int Pop(){
		front++;
		return Array[front];
	}
	public void reset(){
		front=rear=-1;
	}
}
public class Solution {
	static int n , max , index , ans;
	static int map[][];
	static int vis[][];
	static int visGan[][];
	static int diem[];
	static Queue Qx = new Queue(100000);
	static Queue Qy = new Queue(100000);
	static int [] dx = {0,1,0,-1};
	static int [] dy = {1,0,-1,0};
	public static void resetVis(){
		Qx.reset();
		Qy.reset();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				vis[i][j] = 0;
			}
		}
	}
	public static void resetDem(){
		for (int i = 0; i < 6; i++) {
			diem[i] = 0;
		}
		Qx.reset();
		Qy.reset();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				vis[i][j] = 0;
			}
		}
	}
	public static void BFS1 (int x , int y){
		Qx.Push(x);
		Qy.Push(y);
		vis[x][y] = 1;
		while(!Qx.isEmpty()){
			int a = Qx.Pop();
			int b = Qy.Pop();
			for (int i = 0; i < 4; i++) {
				int r = a + dx[i];
				int c = b + dy[i];
				if(r>=0 && c>=0 && r<n && c<n){
					if(map[a][b] == 0 && map[r][c] ==0 && vis[r][c] == 0 && visGan[r][c] == 0) {
						vis[r][c] = 1;
						Qx.Push(r);
						Qy.Push(c);
					}
					if(map[a][b] == 0 && map[r][c] != 0 && vis[r][c] == 0 && visGan[r][c] == 0){
						vis[r][c] = 1;
						Qx.Push(r);
						Qy.Push(c);
						diem[map[r][c]]++;
					}
					if(map[a][b] != 0 && map[a][b] == map[r][c] && vis[r][c] == 0 && visGan[r][c] == 0){
						vis[r][c] = 1;
						Qx.Push(r);
						Qy.Push(c);
						diem[map[r][c]]++;
					}
				}
			}
		}
	}
	public static void BFS2(int x , int y ,int i){
		Qx.Push(x);
		Qy.Push(y);
		visGan[x][y] = 1;
		map[x][y] = i;
		while(!Qx.isEmpty()){
			int a = Qx.Pop();
			int b = Qy.Pop();
			for (int j = 0; j < 4; j++) {
				int r = a + dx[j];
				int c = b + dy[j];
				if(r>=0 && c>=0 && r<n && c<n){
					if(map[r][c] == 0) {
						Qx.Push(r);
						Qy.Push(c);
						map[r][c] = i;
						visGan[r][c] = 1;
					}
				}
			}
		}
	}
	public static void BFS3 (int x , int y){
		Qx.Push(x);
		Qy.Push(y);
		vis[x][y] = 1;
		while(!Qx.isEmpty()){
			int a = Qx.Pop();
			int b = Qy.Pop();
			for (int j = 0; j < 4; j++) {
				int r = a + dx[j];
				int c = b + dy[j];
				if(r>=0 && c>=0 && r<n && c<n){
					if(map[r][c] == map[a][b] && vis[r][c] == 0) {
						vis[r][c] = 1;
						Qx.Push(r);
						Qy.Push(c);
					}
				}
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n = sc.nextInt();
			map = new int [n][n];
			vis = new int [n][n];
			visGan = new int [n][n];
			diem = new int [n*n];
			ans = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					max = 0;
					index = 0;
					if(map[i][j] == 0){
						BFS1(i,j);
						resetVis();
					}
					for (int k = 0; k < n*n; k++) {
						if(max <= diem[k]){
							max = diem[k];
							index = k;
						}
					}
					if(map[i][j] == 0){
						BFS2(i,j,index);
						resetDem();
					}
				}
			}
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (vis[i][j] == 0) {
						BFS3(i,j);
						ans++;
					}
				}
			}
			
//			for (int i = 0; i < n; i++) {
//				for (int j = 0; j < n; j++) {
//					System.out.print(map[i][j]);
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			System.out.println("Case #"+tc);
			System.out.println(ans);
		}
	}
}


////


Case #1
11
Case #2
1
Case #3
31
Case #4
130
Case #5
60
Case #6
44
Case #7
51
Case #8
51
Case #9
47
Case #10
1231
Case #11
1205
Case #12
1224
Case #13
1226
Case #14
1204
Case #15
1234
Case #16
1256
Case #17
1207
Case #18
1227
Case #19
1201
Case #20
1199
Case #21
1176
Case #22
1205
Case #23
1218
Case #24
1215
Case #25
1207
Case #26
1180
Case #27
1159
Case #28
1175
Case #29
1177
Case #30
3129
Case #31
4849
Case #32
4740
Case #33
4721
Case #34
4713
Case #35
4838
Case #36
4792
Case #37
4675
Case #38
4702
Case #39
4778
Case #40
4833
Case #41
4774
Case #42
4778
Case #43
4785
Case #44
4828
Case #45
4764
Case #46
4776
Case #47
4763
Case #48
4724
Case #49
4836
Case #50
4723