[伯俊]BOJ 2630色紙JAVAを作る

BOJ 2630色紙を作る

質問する

下図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行目は青い紙の個数を出力します.

サンプルI/O

ソースコード

import java.util.Scanner;

public class Main {
    private static int n;
    private static int[][] map;
    private static int w, b;

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        getWB(0, n, 0, n);

        System.out.println(w + "\n" + b);

    }

    private static void getWB(int row, int endRow, int col, int endCol) {
        int sum = 0;

        for (int i = row; i < endRow; i++) {
            for (int j = col; j < endCol; j++) {
                sum += map[i][j];
            }
        }

        if (sum == 0) {
            w++;
            return;
        } else if (sum == (endRow - row) * (endCol - col)) {
            b++;
            return;
        }

        getWB(row, (row + endRow) / 2, (col + endCol) / 2, endCol); // 1사분면
        getWB(row, (row + endRow) / 2, col, (col + endCol) / 2); // 2사분면
        getWB((row + endRow) / 2, endRow, col, (col + endCol) / 2); // 3사분면
        getWB((row + endRow) / 2, endRow, (col + endCol) / 2, endCol); // 4사분면

    }
}

Comment

分割征服の代表的な問題.最初は難しいかもしれませんが、感覚があれば解決できます.