작은 정사각형
시간 제한2초메모리 제한512 MB
1x1 또는 제한된 2x2 정사각형을 칠하는 그리드 게임에서 최적 플레이 시 승자를 스프라그-그런디 이론으로 판정하는 문제입니다.
문제
영식이와 민식이는 모눈종이를 색칠하는 게임을 한다. 각 턴에 플레이어는 아직 색칠되지 않은 1×1 정사각형 하나를 색칠하거나, 아직 색칠되지 않은 2×2 정사각형 하나를 색칠할 수 있다. 마지막으로 색칠하는 사람이 승리한다.
단, 2×2 정사각형을 색칠할 때는 위치 제한이 있다. 행 번호를 위에서부터 1, 2, 3, ...으로 매겼을 때, 2×2 정사각형의 위쪽 두 칸은 반드시 홀수 번째 행에 있어야 한다. 즉 2×2 정사각형의 위 행은 1, 3, 5, ...번째 행 중 하나여야 한다.
위 그림의 초록색 배치는 가능한 선택이다.
위 그림의 빨간색 배치는 불가능한 선택이다.
현재 색칠된 칸이 주어진다. 영식이가 먼저 시작하고 두 사람이 모두 최적으로 플레이할 때, 승자를 출력하라.
입력
총 3개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄에는 게임판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 10 이하의 자연수이다. 다음 N개의 줄에는 게임판의 상태가 주어진다. 각 줄은 길이 M의 문자열이며, .은 아직 색칠되지 않은 칸, #은 이미 색칠된 칸을 의미한다.
출력
각 테스트 케이스마다 영식이가 이기면 Y, 민식이가 이기면 M을 한 줄에 하나씩 출력한다.