체스판 다시 칠하기

• N,M의 범위가 작고 자를 크기가 고정되어 있으므로, 그냥 모든 8*8 영역에 대해서 다시칠할 갯수를 구해보는 브루트포스 방식으로도 푸는데에는 지장이 없다. 영역 한개에 대해서 계산하는 것은 O(8*8)=O(1) 이고, 영역은 O(N*M)개가 있으므로 총 시간복잡도는 O(NM).
• 체스판 다시 칠하기 2는 이 문제를 단순 브루트포스가 불가능하도록 확장한 문제이다.

"""Solution code for "BOJ 1018. 체스판 다시 칠하기".

- Problem link: https://www.acmicpc.net/problem/1018
- Solution link: http://www.teferi.net/ps/problems/boj/1018
"""


def main():
    N, M = [int(x) for x in input().split()]
    board = [input() for _ in range(N)]
    min_count = 64
    for y in range(N - 7):
        for x in range(M - 7):
            t = 'W'
            count = 0
            for xx in range(8):
                for yy in range(8):
                    if board[y + yy][x + xx] == t:
                        count += 1
                    t = 'B' if t == 'W' else 'W'
                t = 'B' if t == 'W' else 'W'
            min_count = min(min_count, count, 64 - count)
    print(min_count)


if __name__ == '__main__':
    main()