시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB4621188926.807%

문제

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

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

초록색과 같이 칠하는 것은 가능한 방법이다.

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

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

입력

총 세 개의 테스트 케이스가 입력으로 주어진다.

각 테스트 케이스의  첫째 줄에 게임 판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 10보다 작거나 같은 자연수이다. 둘째 줄부터 모눈종이의 정보가 주어진다. 총 N개의 줄에 M개의 문자가 주어지며, “.”은 아직 색칠되지 않은 칸, “#”은 현재 색칠이 되어있는 칸을 의미한다.

출력

각 테스트 케이스마다 영식이가 이기면 Y를, 민식이가 이기면 M을 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

Y
Y
M
  • 첫 번째 테스트 케이스: 영식이가 2×2 크기의 정사각형을 색칠하면, 민식이는 색칙할 수 있는 방법이 없다. 따라서, 영식이가 이긴다.
  • 두 번째 테스트 케이스: 영식이가 2×2 크기의 정사각형을 (1, 1)부터 색칠하면, 민식이가 1×1 크기의 정사각형을 그릴 수 있게 되어 영식이가 진다. 하지만 영식이가 (1, 1)에 1×1 크기의 정사각형을 색칠하면, 남은 방법은 1×1 크기의 정사각형을 색칠하는 것 밖에 없다. 따라서, 4턴이 진행되고 영식이가 이기게 된다.

(i,j)는 위에서부터 i번째 줄, 왼쪽에서부터 j번째 칸을 의미한다.

예제 입력 2

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

예제 출력 2

Y
M
Y

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: h0ngjun7
  • 데이터를 추가한 사람: yooshnn