BOJ 2630色紙を作る

質問する

BOJ 2630色紙を作る
シルバーIII|白駿2630|Python 3 Python池

アルゴリズム#アルゴリズム#

BOJ 1780用紙数題によく似ています.( BOJ 1780段ボール箱数-段ボール箱 )
この問題の問題は細かく書いてあるので,そのまま体現すればよい.

この紙の場合

上の写真と一緒にシェアすればいいです.
各紙を4等分し、そのグループが同じ値(1または0)で構成されている場合は、分割する必要はありません.
Pythonの2次元リストスクライブを用いて,再帰関数を4つの正方形グループに分けた.

check([row[:c//2] for row in part[:c//2]], c//2)
check([row[:c//2] for row in part[c//2:]], c//2)
check([row[c//2:] for row in part[:c//2]], c//2)
check([row[c//2:] for row in part[c//2:]], c//2)

コード#コード#

import sys

input = sys.stdin.readline

blue = 0  # 1 갸수
white = 0 # 0 개수

# 파란색(1)의 개수를 세는 함수
def count_blue(part, c):
    count = 0
    for i in range(c):
        for j in range(c):
            if part[i][j] == 1:
                count += 1

    return count


def check(part, c):
    global blue, white
    # 1x1 크기라면
    if c == 1:
        if part[0][0] == 1:
            blue += 1
        else:
            white += 1
        return
	
    # 전부 파란색(1)이라면
    if count_blue(part, c) == c * c:
        blue += 1
        return
    # 전부 흰색(0)이라면
    elif count_blue(part, c) == 0:
        white += 1
        return
    
    # 정사각형 4개 그룹으로 나누어 재귀 호출
    else:
        check([row[:c//2] for row in part[:c//2]], c//2)
        check([row[:c//2] for row in part[c//2:]], c//2)
        check([row[c//2:] for row in part[:c//2]], c//2)
        check([row[c//2:] for row in part[c//2:]], c//2)
    

N = int(input())
p = [list(map(int, input().split())) for _ in range(N)]

check(p, N)

print(white)
print(blue)

結果