白俊解答-チェス盤を1018回塗り直す

📜 理解问题

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

💡 問題の再定義

任意に色を塗った回路基板を8 x 8サイズに切る場合、色を塗った矩形の最小値が必要です.

▼▼▼計画作成

この問題は8×8のサイズで一つ一つカットして、中に塗るところを数える方法で解決できます.つまり、ブルートフォスが一つ一つ確認する方法で実現します.この場合,色付きの行+列が偶数か奇数かを選択し,前の2つの場合の数字を考慮する.

💻 計画の実行

if __name__ == '__main__':
    N, M = map(int, input().split())

    chess_board = []
    for _ in range(N):
        chess_board.append(input())

    cnt_list = []
    for row in range(N - 7):
        for col in range(M - 7):
            cnt1 = 0
            cnt2 = 0
            for i in range(row, row + 8):
                for j in range(col, col + 8):
                    if (i + j) % 2 == 0:
                        if chess_board[i][j] == 'W':
                            cnt1 += 1
                        if chess_board[i][j] == 'B':
                            cnt2 += 1
                    else:
                        if chess_board[i][j] == 'B':
                            cnt1 += 1
                        if chess_board[i][j] == 'W':
                            cnt2 += 1
            cnt_list.append(cnt1)
            cnt_list.append(cnt2)
    print(min(cnt_list))

🤔 振り返る

Brootforceで問題を解決する方法なので難しくはありませんが、最初に実現したときは上記のような行と列の加算ではなく、左上隅の値と比較します.上図に示すように、2つの場合、上記のコードはずっと簡潔になっているようです.