[伯俊]チェスパンダ試塗/1018号/Python/ブルートフォードアルゴリズム

1697 ワード

💡質問する


志敏は自分の邸宅でMxNサイズの碁盤を見つけた.一部の正方形は黒に塗り、残りは白に塗ります.志敏はこの碁盤を8×8の大きさの碁盤に切りたいと思っている.
チェスの碁盤は白黒の間にあるべきだ.具体的には、各セルは白黒の1つに塗り、共有エッジの2つの長方形は異なる色に塗ります.したがって,この定義によれば,チェス盤が色付く場合は2つしかない.一つは左上の格子が白で、一つは黒です.
ボードの上のボードがボードのようになる保証がないので、志敏は8×8の大きさのボードに切った後、正方形を塗り直すと思っています.もちろん、8 x 8サイズは自由に選べます.プログラムを書いて、志敏が塗り直す正方形の最小個数を求めます.

入力


1行目はNとMです.NとMは8以上、50以下の自然数である.2行目からN行目まで、板上の各行の状態が与えられる.Bは黒、Wは白です.

しゅつりょく


最初の行は、志敏が塗り直す正方形の個数の最大値を出力します.
入力例
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB
サンプル出力
12

📖私が書いたコード

n,m=map(int,input().split())
chess=[input() for _ in range(n)]

# m*n체스판
minimum=64
for i in range(n-7):
    for j in range(m-7):
        #첫 시작점
        cnt1,cnt2=0,0
        for k in range(i,i+8):
            for l in range(j,j+8):
                    #k+l이 짝수인것끼리 동일
                    if (k+l)%2==0:  #짝수일 경우
                        if chess[k][l]!="W":
                            cnt1+=1  #다시 칠해야하는 갯수
                        else:
                            cnt2+=1
                    else:  #홀수일 경우
                        if chess[k][l]!="B":
                            cnt1+=1  #다시 칠해야하는 갯수
                        else:
                            cnt2+=1

        if minimum> min(cnt1,cnt2):
            minimum=min(cnt1,cnt2)
print(minimum)
質問元:https://www.acmicpc.net/problem/1018