質問する

下図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と各正方形のセルの色(白または青)を入力すると、カットされた白と青の用紙の個数を計算するプログラムを作成します.

コード#コード#

import sys
input = sys.stdin.readline

def divideSquare(square):
	
	same = False
	first = square[0][0]
	
	if len(square) == 1:
		return "B" if first == "1" else "W"
	
	firstSquare = [row[0: len(square)//2] for row in square[0 : len(square)//2]]
	secondSquare = [row[len(square)//2 : len(square)] for row in square[0:len(square)//2]]
	thirdSquare = [row[0: len(square)//2] for row in square[len(square)//2: len(square)]]
	fourthSquare = [row[len(square)//2: len(square)] for row in square[len(square)//2 : len(square)]]
	
	
	for i in range(len(square)):
		for j in range(len(square[0])):
			if square[i][j] != first:
				return divideSquare(firstSquare)+ divideSquare(secondSquare)+divideSquare(thirdSquare)+divideSquare(fourthSquare)
					
	return "B" if first == "1" else "W"
	

arr = list()
n = int(input())

for i in range(n):
	inpt = list(map(str, input().split()))
	
	arr.append(inpt)

ans= divideSquare(arr)

print(ans.count("W"))
print(ans.count("B"))

説明:

コードを書く時間は、難易度に比べて非常に長い.再帰関数を使用して2 D配列全体を検索し、すべてが同じ色でない場合は4等分で4つの関数を呼び出します.すべての要素が同じか、紙が1*1の前に再帰的に呼び出され、条件が満たされると、紙の色「B」または「w」が返され、数字で返されると、どちらが白か青かを区別するのが難しい場合があるので、文字列を返し、返された文字列から「B」の個数と「W」の個数を出力します.