#2630色紙[白駿](H 99.34)

📄質問する

下図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

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

サンプル出力1

9
7

🖋️コード#コード#

import sys

n = int(sys.stdin.readline())
result = []
graph = []
white = 0
blue = 0
for _ in range(n):
        graph.append(list(map(int, sys.stdin.readline().split())))

def cutting (x,y,n):
    global white
    global blue
    color = graph[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != graph[i][j]:
                cutting(x, y, n // 2)
                cutting(x, y + n//2, n // 2)
                cutting(x + n // 2, y, n // 2)
                cutting(x + n // 2, y + n // 2, n // 2)
                return
    if color == 0:
        white += 1
    else:
        blue += 1


cutting(0,0,n)
print(white)
print(blue)

🧷追加の説明

最左上隅のブロックx,yから順に他のブロックx,yを比較する.
合わないブロックがある瞬間.
4点に切り、合わなければ4点を加え、同じ色が見つかれば白か青が1アップします.