타일 놓기

• 설명은 조금 다르지만 보드 색칠하기와 동일한 것을 구하는 문제이고. 구해야 하는 N과 M의 크기만 작아졌다.
• 비트 스크롤링 DP와 이분 매칭 (Bipartite Matching)으로 푸는 두가지 풀이가 있다. 이 문제에서는 두 방법 다 통과 가능하고, 보드 색칠하기에서는 이분매칭 방법만 통과 가능하다. 여기서는 비트스크롤링 DP 풀이만 설명. 이분매칭 풀이는 보드 색칠하기를 참고.
• 각 셀을 가로방향 타일 또는 세로방향 타일들로 채운다고 생각하자. 가로방향 타일이 가로방향으로 연속되게 놓여있으면 하나의 타일로 묶을수 있고, 세로방향 타일이 세로방향으로 연속되게 놓여있어도 마찬가지 하나의 타일로 묶을수 있다고 생각하자.
• i번째 셀까지 타일을 놓을때 사용된 총 타일의 갯수를 점화식으로 세워보자. i번째 셀에 가로방향 타일을 붙인다면, 현재 셀의 왼쪽 셀의 타일이 가로방향이면 추가 타일이 필요없고, 세로방향이면 추가 타일이 필요하다. i번째 셀에 세로방향 타일을 붙인다면, 현재 셀의 위쪽 셀의 타일이 가로방향이면 추가 타일이 필요하고, 세로방향이면 추가 타일이 필요없다. 즉, 왼쪽과 위쪽셀에만 영향을 받으므로, 최근 M개 셀의 타일형태를 스테이트로 갖는 DP테이블을 구성해서 풀게되는 전형적인 비트스크롤링 DP가 된다.
• 2^M개의 스테이트에 대한 최소 타일수를 저장하는 DP테이블을 유지하면서, M*N개 셀을 이터레이션하면서 테이블을 업데이트해주면 되니까. 총 시간복잡도는 O(2^M*M*N)이 된다.

"""Solution code for "BOJ 14390. 타일 놓기".

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

Tags: [DP]
"""

INF = float('inf')
PILLAR = '#'
EMPTY = '.'


def main():
    N, M = [int(x) for x in input().split()]
    board = [input() for _ in range(N)]

    state_size = 1 << M
    mask = state_size - 1
    first_bit = 1 << (M - 1)
    dp_cur = [0] * state_size
    for r, row in enumerate(board):
        for c, val in enumerate(row):
            dp_prev, dp_cur = dp_cur, [INF] * state_size
            for state_prev, dp_val in enumerate(dp_prev):
                state_cur_v = (state_prev << 1) & mask
                state_cur_h = state_cur_v + 1
                if val == PILLAR:
                    dp_cur[state_cur_v] = min(dp_cur[state_cur_v], dp_val)
                    dp_cur[state_cur_h] = min(dp_cur[state_cur_h], dp_val)
                else:
                    is_connected_v = (r > 0 and board[r - 1][c] == EMPTY and
                                      (state_prev & first_bit) == 0)
                    is_connected_h = (c > 0 and board[r][c - 1] == EMPTY and
                                      (state_prev & 1) == 1)
                    dp_cur[state_cur_v] = min(
                        dp_cur[state_cur_v],
                        dp_val if is_connected_v else dp_val + 1)
                    dp_cur[state_cur_h] = min(
                        dp_cur[state_cur_h],
                        dp_val if is_connected_h else dp_val + 1)

    print(min(dp_cur))


if __name__ == '__main__':
    main()