작은 정사각형

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

"""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()