白準1018号:チェス盤を塗り直す


質問する


題ショートカットキー>白準1018号:チェス盤を塗り直す

に答える


Brotforceアルゴリズムを用いて解く.(8*8間のメッシュが移動し、最小値が更新されます!)
このとき注意しなければならないのは2つの状況があることです.第1のケースは、第1の文字が変更されないと仮定し、第2のケース(64−第1のケース)は、第1の文字が変更されたと仮定する.
import sys
N, M = map(int, input().split())
chess = list()
for i in range(N):
    chess.append(sys.stdin.readline().rstrip())
ans = 32
for i in range(N-7):
    for j in range(M-7):
        repaint = 0
        begin_chr=chess[i][j] 
        if begin_chr == 'B':
            scnd_chr = 'W'
        else:
            scnd_chr = 'B'
        begin_mod2=(i+j)%2
        for k in range(i, i+8):
            for l in range(j, j+8):
                if (k+l)%2==begin_mod2:
                    if chess[k][l]!=begin_chr:
                        repaint+=1
                else:
                    if chess[k][l]!=scnd_chr:
                        repaint+=1
        ans = min(ans, repaint, 64-repaint)
print(ans)