moner_ari   9달 전

[문제]

2인용 보드게임 Wall Making Game이 요즘 선풍적인 인기를 끌고 있다.

이 게임은 $H$×$W$ 격자판에서 진행된다. 격자판의 각 칸은 비어 있거나, X자로 표시되어 있거나, 벽 중 어느 하나이다. 게임이 시작될 때에는, 격자판의 어떤 칸도 벽이 아니다.

이 게임에서, 2명의 플레이어는 번갈아가며 다음과 같이 턴을 진행한다.

  1. 턴을 진행하는 플레이어는 (벽도 아니고 X자도 표시되지 않은) 빈 칸 중 하나를 선택한다. 빈 칸을 선택할 수 없다면, 현재 턴을 진행하는 플레이어는 패배한다.
  2. 1번 과정에서 선택한 칸을 포함해서, 상하좌우 4개 방향으로 벽을 만나거나 격자판을 벗어날 때까지 만나는 모든 칸을 벽으로 바꾼다.

이때 1번 과정에서 X자로 표시된 칸들은 선택될 수 없으나, 2번 과정에 의해 X자로 표시된 칸들이 벽으로 바뀔 수 있다는 점에 유의하라.

<그림 1>은 현재 플레이어가 3번 행, 4번 열의 칸을 선택했을 때의 게임판의 변화를 보여준다.

<그림 1> - Wall Making Game에서의 한 턴의 진행 예시. 그림 생략.

2명의 플레이어가 최선을 다해 게임을 진행할 때, 누가 게임에서 승리하는지 판별하는 프로그램을 작성하시오.

--------

[입력]

입력의 1번째 줄에는 2개의 정수 $H$와 $W$가 주어진다. (1 ≤ $H$, $W$ ≤ 20) $H$, $W$는 각각 게임판의 세로, 가로 길이를 나타낸다. 다음 $H$개 줄에는 게임을 시작할 때의 게임판의 상태 정보가 주어진다. 이때 $H$개 줄은 각각 $W$개 문자로 구성되어 있다.

$i$번 행, $j$번 열의 칸이 비어 있다면 $i$번째 줄의 $j$번째 문자는 '.'이며, X자로 표시되어 있다면 'X'이다. (1 ≤ $i$ ≤ $H$, 1 ≤ $j$ ≤ $W$)

--------

[출력]

입력으로 주어진 게임판에서 자신의 턴을 먼저 진행하는 플레이어가 승리한다면 "First"를, 나중에 턴을 진행하는 플레이어가 승리한다면 "Second"를 한 줄에 출력한다. 이때 큰따옴표("")는 출력하지 않는다.

댓글을 작성하려면 로그인해야 합니다.