Cutting a piece
user_9175993
plain_text
a year ago
2.1 kB
4
Indexable
import java.util.Scanner; public class PaperCutting { // Hàm đệ quy để đếm số lượng giấy trắng và xanh static int[] countColoredPieces(int[][] paper, int x, int y, int size) { if (isUniform(paper, x, y, size)) { if (paper[x][y] == 0) { return new int[]{1, 0}; // {white, blue} } else { return new int[]{0, 1}; // {white, blue} } } else { int newSize = size / 2; int[] count1 = countColoredPieces(paper, x, y, newSize); int[] count2 = countColoredPieces(paper, x, y + newSize, newSize); int[] count3 = countColoredPieces(paper, x + newSize, y, newSize); int[] count4 = countColoredPieces(paper, x + newSize, y + newSize, newSize); return new int[]{ count1[0] + count2[0] + count3[0] + count4[0], count1[1] + count2[1] + count3[1] + count4[1] }; } } // Hàm kiểm tra nếu tất cả các phần của giấy có cùng màu static boolean isUniform(int[][] paper, int x, int y, int size) { int color = paper[x][y]; for (int i = x; i < x + size; i++) { for (int j = y; j < y + size; j++) { if (paper[i][j] != color) { return false; } } } return true; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t <= T; t++) { int N = sc.nextInt(); int[][] paper = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { paper[i][j] = sc.nextInt(); } } int[] result = countColoredPieces(paper, 0, 0, N); System.out.println("Case #" + t); System.out.println(result[0] + " " + result[1]); } sc.close(); } }
Editor is loading...
Leave a Comment