[BOJ 2630]カラーペーパーの作成(Python)

10678 ワード
分割征服 白駿 テキストリンク

質問する


https://www.acmicpc.net/problem/2630

これは、綿のすべての格子が同じ色になるまで、カラー紙を1/4に分割してきた問題です.
青白い紙の個数をプリントアウトすればいいです.

問題を解く


0.取得入力
n = int(input())
papers = []

for _ in range(n):
    row = list(map(int,input().rsplit()))
    papers.append(row)
1.現在のセルと異なる色の場合は、1/4に分けます.
# 현재 칸 색상
curr = papers[row][col]

for i in range(row, row + n):
    for j in range(col, col + n):
        if curr != papers[i][j]:
            # 길이를 절반으로 나눈다.
            next_n = n // 2
            
            check(row, col, next_n) # 1
            check(row, col + next_n, next_n) # 2
            check(row + next_n, col, next_n) # 3
            check(row + next_n, col + next_n, next_n) # 4
            return
2.現在のバーの色から個数を追加
# 현재 칸 색상이 흰 색이면
if curr == 0:
    white_cnt += 1
# 현재 칸 색상이 파란색이면
else:
    blue_cnt += 1
return

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
papers = []

for _ in range(n):
    row = list(map(int,input().rsplit()))
    papers.append(row)

blue_cnt, white_cnt = 0, 0

def check(row,col,n):
    global blue_cnt, white_cnt

    curr = papers[row][col]
    for i in range(row, row + n):
        for j in range(col, col + n):
            if curr != papers[i][j]:
                next_n = n // 2
                check(row, col, next_n)
                check(row, col + next_n, next_n)
                check(row + next_n, col, next_n)
                check(row + next_n, col + next_n, next_n)
                return
    if curr == 0:
        white_cnt += 1
    else:
        blue_cnt += 1
    return

check(0,0,n)
print(white_cnt)
print(blue_cnt)
Swift)ARC
JavaScript関数