====== 작은 정사각형 ======

===== 풀이 =====
  * 좀 막막했는데, 2×2 크기의 정사각형의 위의 절반은 반드시 홀수번째 줄에 색칠해야 한다는 것이 중요한 힌트였다.
  * 이 조건덕분에, 보드를 2줄씩 나눠서 게임을 진행해도 똑같은 게임이 된다. 즉, 2줄단위로 나눠서 각각에 대해서 그런디 수를 구하고, 이것들을 모두 xor해서 전체 게임판의 그런디수를 구할수 있다.
  * 2줄짜리 게임판에 대해서 그런디수를 구하는 것은, 가로 길이가 작으므로 그냥 게임판 전체 길이에 대해서 dp로 구해버려도 계산이 가능하긴 하다. 
  * 하지만 좀더 효율적으로 구하려면, 세로길이가 2인 영역들만 따로 분리해서 그런디수를 구하는 것이다. 세로길이가 1인 영역들에는 1x1 블럭을 놓는 것밖에 할수 없고 다른 영역에 영향을 미치지 못하므로 이것들도 분리해서 다른 독립적인 게임들이라고 생각해버려도 된다. 그러면 2줄짜리 게임판 하나를 다시 1x1칸 x개, 2x(w_1)칸, 2x(w_2)칸, ..., 2x(w_n)칸 으로 분리해서, 각각에 대해 그런디수를 구하고 xor해서 계산할수 있다.
  * 2x(w) 칸에 대한 그런디수 g[w] 을 구하는 것은 간단하다. 가능한 액션은 2x2짜리 블럭을 놓아서 2*i칸과 2*(w-i-2)칸으로 분할하는 것 (i>=0)과 1x1짜리 블럭을 놓아서 2xi칸과 2x(w-i-1)칸과 1x1 칸으로 분할하는 것의 두 종류이다. 이것들에 대해서 그런디수를 dp로 구해주면 된다. O(w^2)에 처리 가능
  * 그런디수를 M까지 O(M^2)에 구하고 나면, 나머지 필요한 작업은 보드를 분할해주는것뿐이다. 보드를 한번 스캔하면서 처리 가능하므로 O(N*M)이 걸린다. 총 시간복잡도는 O(M*(N+M))


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1603. 작은 정사각형".

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

Tags: [Game theory]
"""

import functools
import itertools


EMPTY = '.'


@functools.cache
def compute_grundy(n):
    if n <= 1:
        return 0
    next_grundy_nums = {
        compute_grundy(i) ^ compute_grundy(n - i - 2) for i in range(n - 1)
    } | {compute_grundy(i) ^ compute_grundy(n - i - 1) ^ 1 for i in range(n)}
    return next(x for x in itertools.count() if x not in next_grundy_nums)


def main():
    for _ in range(3):
        # pylint: disable=unused-variable
        N, M = [int(x) for x in input().split()]
        board = [input() for _ in range(N)]

        tall_block_widths = []
        small_block_count = 0
        for row1, row2 in zip(board[::2], board[1::2]):
            for key, group in itertools.groupby(zip(row1, row2)):
                if key == (EMPTY, EMPTY):
                    tall_block_widths.append(len(list(group)))
                elif EMPTY in key:
                    small_block_count += len(list(group))
        if N % 2 == 1:
            small_block_count += board[-1].count(EMPTY)

        tot_grundy = small_block_count % 2
        for width in tall_block_widths:
            tot_grundy ^= compute_grundy(width)
        print('Y' if tot_grundy > 0 else 'M')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_2}}