[白俊]2630号カラーペーパーを作る

質問リンク:https://www.acmicpc.net/problem/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行目は青い紙の個数を出力します.

問題を理解する

これは分割征服問題である.
同じ色の長方形が現れるまで、4つの部分に分かれている問題です.
矩形の個数を数える問題です
入力された場合、入力された部分が同じ色に塗られているかどうかを確認し、そうでなければ4つの部分に分けます.

コード実装（C++）

#include <iostream>

using namespace std;

int map[128][128];
int blueCnt = 0;
int whiteCnt = 0;

bool check(int x, int y, int n){
    int temp = map[y][x];
    for(int i = y ; i < y+n ; i++){
        for(int j = x ; j < x+n ; j++){
            if(map[i][j] != temp) return false;
        }
    }
    return true;
}
void divide(int x, int y, int n){
    if(!check(x, y, n)){
        divide(x, y, n/2); //left
        divide(x + n/2, y, n/2); // right
        divide(x, y + n/2, n/2);  //low
        divide(x + n/2, y + n/2, n/2); //low
    }
    else {
        map[y][x] ? blueCnt++ : whiteCnt++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    int num;
    cin >> num;
    for(int i = 0 ; i < num ; i++){
        for(int j = 0 ; j < num ; j++){
            cin >> map[i][j];
        }
    }
    divide(0, 0, num);
    cout << whiteCnt << "\n" << blueCnt << "\n";
}

評価

今から分割征服が始まりました.暴力を振るう時の考え方とは少し違って、これまでのところ、実施方法を考え出すのは難しいようだ.