Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
8
Indexable
Never
import java.io.FileInputStream;
import java.util.Scanner;

public class CuttingaPieceofColoredPaper {
	static int a[][];
	static int N;
	static int bluePaper;
	static int whitePaper;

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("QueenMaximumScore"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			a = new int[N][N];
			// 0; trang
			// 1: xanh
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			bluePaper = 0; // reset sau moi Tc
			whitePaper = 0;
			backTrack(0, 0,N);
			System.out.println("Case #" + test_case);
			System.out.println(whitePaper+" "+bluePaper);
		}
	}


	public static void demMau(int row, int col) {
		if (a[row][col] == 1)
			bluePaper++;
		else {
			whitePaper++;
		}
	}

	public static boolean checkFullColorPaper(int row, int col, int n) {
		for (int i = row; i < row + n; i++)
			for (int j = col; j < col + n; j++)
				if (a[i][j] != a[row][col])
					return false;
		return true;
	}

	public static void backTrack(int row, int col, int N) {
		if (N == 1) {
			demMau(row, col);
			return;
		}

		if (checkFullColorPaper(row, col, N)) {
			demMau(row, col);
			return;
		}
		int newSize = N / 2; 
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				int newRow = row + newSize * i;
				int newCol = col + newSize * j;
				backTrack(newRow, newCol, newSize);
			}
		}
		
//		for(int i = 0; i<4;i++)
//		{
//			int newRow = (i==0||i==1)?row:(row+N/2);
//			int newCol = col;
//			switch (i) {
//				case 0:
//				case 1:
//				case 2:
//					newCol=col;
//					break;
//				case 3:
//					newCol = col+N/2;
//					break;
//			}
//			backTrack(newRow, newCol, newSize);
//		}

	}

}