[Algorithm] 📜白準2630色紙を作る

0、問題

下図1に示すように、正方形の格子からなる正方形紙が複数あり、各正方形は白または青に塗られている.与えられた紙を一定の規則に従って様々な大きさの正方形の白色または青色の紙に切る.
全紙サイズN×N(N=2 k,kは1以上7以下の自然数)の場合、切り紙のルールは以下の通りです.
用紙全体に同じ色が塗られていない場合は、<図2>のI,II,III,IVのように、中央部分を横方向と縦方向にカットしてください.× n/2は色紙に分かれている.分割された用紙I,II,III,IVについては,前のようにすべて同じ色を塗らなければ,同じ方法で同じ大きさの4つのカラー紙に分けられる.この過程を繰り返して、紙を全部白や青に塗ったり、正方形の格子になったりして、これ以上裁断できないまで繰り返します.
上記のルールに従って裁断する場合、『図3』は『図1』の用紙が1回目に分割された状態を示し、『図4』は2回目に分割された状態を示し、『図5』は最終的に作られた9枚の異なる大きさの白い用紙と7枚の青い紙を示した.
所定の用紙の長さNと各正方形のセルの色(白または青)を入力すると、カットされた白と青の用紙の個数を計算するプログラムを作成します.
入力
1行目は紙全体の片側長Nがある.Nは、2、4、8、16、32、64、128のうちの1つである.色紙の各横線の正方形の格子の色は、上から2行目から最後の行まで順番に変わります.白い格子は0で、青い格子は1で、数字の間にスペースがあります.
しゅつりょく
1行目はカットされた白い紙の個数、2行目は青い紙の個数を出力します.

1.問題の簡単な説明

同じ領域の色が異なる場合は、クリップし、最後に残った破片の数を色で計算して印刷します.

2.アイデア

分割征服

3.コア解答

1)分割征服

for(int i=0; i<2; i++) {
				for(int j=0; j<2; j++) {
					fold(x+size*j, y+size*i, size);
				}
}

4.コード

import java.io.*;
public class Divide_3 {
	static int arr[][];
	static int white = 0, blue = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		
		for(int i=0; i<n; i++) {
			String s[] = br.readLine().split(" ");
			for(int j=0; j<n; j++) {
				arr[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		fold(0,0,n);
		
		System.out.println(white);
		System.out.println(blue);
	}
	
	static void fold(int x, int y, int size) {
		if(!check(x,y,size)) {
			size/=2;
			
			for(int i=0; i<2; i++) {
				for(int j=0; j<2; j++) {
					fold(x+size*j, y+size*i, size);
				}
			}
		}
	}
	
	static boolean check(int x, int y, int size) {
		for(int i=y; i<y+size; i++) {
			for(int j=x; j<x+size; j++) {
				if(arr[y][x] != arr[i][j])
					return false;
			}
		}
		
		if(arr[y][x] == 1)
			blue++;
		else
			white++;
		
		return true;
	}

}

5.結果

成功～