시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 125 24 14 18.182%

문제

영식이와 민식이는 모눈종이를 색칠하는 유치한 게임을 하기로 했다. 매 턴마다 영식이와 민식이는 비어있는 1*1크기의 정사각형이나, 비어있는 2*2크기의 정사각형을 색칠 할 수 있다. 정사각형을 가장 마지막에 칠하는 사람이 이 게임의 승자가 되는 것이다.

이 게임에서 정사각형을 칠할 때에는 조건이 한 가지 있는데, 모눈종이의 가장 위부터 차례대로 1번째 줄, 2번째 줄, 이렇게 번호를 매겼을 때, 2*2크기의 정사각형의 위의 절반은 반드시 홀수번째 줄에 칠해져야 한다는 소리다.

초록색과 같이 칠하는 것은 가능한 색칠이고,

빨간색과 같이 칠하는 것은 불가능하다.

현재 모눈종이에 색칠된 칸이 주어지고, 영식이와 민식이가 항상 최적의 방법으로 게임을 한다고 할 때, 이기는 사람을 출력하는 프로그램을 작성하시오. 항상 영식이가 게임을 먼저 시작한다.

입력

첫째 줄에 게임 판의 세로크기 N과 가로크기 M이 주어진다. N과 M은 10보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. “.”은 아직 색칠되지 않은 칸이고, “#”은 현재 색칠이 되어있는 칸이다. 위와 같이 총 3번 들어온다.

출력

첫째 줄에 첫 번째 게임을 영식이가 이기면 Y를, 민식이가 이기면 M을 출력한다. 둘째 줄, 셋째 줄도 첫째 줄과 마찬가지로 출력한다.

예제 입력

2 2
..
..
2 4
...#
..##
4 2
..
..
..
..

예제 출력

Y
Y
M

힌트

첫 번째 게임은 영식이가 2*2크기의 정사각형을 색칠하자마자 이기게 된다. 두 번째 게임에서 영식이가 만약에 2*2크기의 정사각형을 (1,1)부터 색칠하게 되면 민식이가 1*1크기의 정사각형을 그릴 수 있게 되어 영식이가 지게 된다. 하지만 영식이가 (1,1)에 색칠하게 되면, 어떻게 하든 영식이가 이기게 된다. 편의상 도입한 좌표는 (i,j)는 위에서부터 i번째 줄, 왼쪽에서부터 j번째 칸을 의미한다. 세 번째 게임에서는 설명이 필요하면 생각을 해보자.

출처

  • 문제의 오타를 찾은 사람: appa
  • 문제를 번역한 사람: baekjoon