만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

강 게임

시간 제한0.5초메모리 제한512 MB

요약
두 사람이 습지 격자에 카메라를 번갈아 놓으며, 누가 이기는지 최적 전략으로 판단합니다.
난이도

보통10점 중 7점

유형
게임 이론, 그래프, 조합론
정답자
아직 제출이 없습니다

문제

친구 조류학자와 함께 희귀한 새가 나타나기를 기다리며 습지에서 몇 시간씩 새를 관찰하고 있다. 시간을 보내려고 작은 게임을 만들었다. 습지는 평지, 젖은 구역, 보호 구역의 세 종류 칸으로 이루어진 N×NN \times N 격자이다.

서로 연결된 젖은 구역 칸들은 습지 영역을 이룬다. 습지 영역은 젖은 구역 칸들의 극대 집합이며, 영역 안의 어떤 칸에서든 연결된 젖은 구역 칸들을 따라 영역 안의 다른 칸으로 갈 수 있다. 두 칸은 변을 공유할 때 연결되며, 따라서 격자의 가장자리가 아닌 칸은 다른 4칸과 연결된다. 각 습지 영역은 격자의 왼쪽 변과 오른쪽 변에 모두 연결되어야 하며, 젖은 구역 칸을 2N2N개보다 많이 포함하지 않는다. 서로 다른 두 습지 영역에 속한 젖은 구역 칸들은 항상 가로 또는 세로로 이동하는 거리가 3 이상이다. 예를 들어 아래 두 예시에서 파란색 칸들은 서로 거리가 3이다.

두 사람은 번갈아 다음 조건을 지키며 습지에 카메라를 설치한다.

  • 카메라는 평지 칸에 놓아야 한다.
  • 카메라는 새 사진을 찍을 수 있도록 젖은 구역 칸에 인접해야 한다.
  • 카메라는 보호 구역 칸에 놓을 수 없다.
  • 같은 칸에 카메라 두 대를 놓을 수 없다.
  • 같은 습지 영역에 인접한 두 카메라는 서로 인접할 수 없다. 인접은 변을 공유하는 것을 뜻한다.

카메라를 더 놓을 수 없게 된 첫 번째 플레이어가 게임에서 진다.

두 플레이어가 최선을 다한다면 선공이 이기는가, 지는가?

입력

입력은 다음 줄로 구성된다.

  • 첫 줄에 정수 NN이 주어진다.
  • 다음 NN개 줄에는 격자의 한 행을 나타내는 문자열이 주어진다. \*는 젖은 구역 칸, .는 평지 칸, x는 보호 구역 칸을 나타낸다.

출력

두 플레이어가 최선을 다할 때 선공이 이기면 First player will win을, 그렇지 않으면 Second player will win을 출력한다.

제한

입력은 1≤N≤101 \le N \le 10을 만족한다.

예제2

  1. 예제 1

    입력
    3
    ...
    ...
    ***
    
    예상 출력
    First player will win
    
  2. 예제 2

    입력
    10
    **********
    *.x.*.....
    *...*.....
    *****.....
    ..........
    ..........
    xx******..
    ***x...*..
    ..*...x*.x
    ..********
    
    예상 출력
    Second player will win