시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 40 | 8 | 5 | 14.706% |
드록바와 셰브첸코가 첼시에서 같이 훈련하던 옛날 옛적 어느 날 두 선수는 훈련에 지쳐 다음과 같은 게임을 하며 쉬기로 한다.
편의상 두 플레이어를 A, B라고 부를 때, 두 플레이어는 N*N짜리 정사각형 보드의 한 점에서 시작하게 된다.
그래서 A, B는 각각 시작점을 가지게 되고 보드에는 흰 칸과 검은 칸이 있는데 검은 칸은 지나가지 못하는 칸이다.(물론 A, B의 시작점과 검은 칸이 겹치는 경우는 없다.)
플레이어들은 각 턴마다 상, 하, 좌, 우로 한 번씩 움직일 수 있다. 그리고 만약 플레이어가 움직여서 상대방의 현 위치와 겹치게 되면 그 플레이어는 상, 하, 좌, 우중 한 방향으로 한 번 더 움직일 수 있는 기회를 받는다.
A플레이어가 먼저 턴을 시작한다고 할 때 상대방의 시작점으로 먼저 도착하는 사람이 경기의 승자가 된다. 양 선수는 최선의 전략을 사용한다고 가정할 때 누가 승자가 될지 알아 보아라.
첫째 줄에는 테스트 데이터의 개수 t (1<=t<=10)가 들어온다. 그리고 다음 t개의 세트에는 우선 맵의 크기 n(1<=n<=300)이 주어지고 다음에는 N*N짜리 지도가 주어지는데 A의 위치와 B의 위치가 표시되어있고 흰자리는 ‘.’, 검은 자리는 ‘#’으로 표시되어있다.
누가 승리할지 테스트 케이스 순서대로 출력하여라.
2 4 A... .#.. .... ...B 4 A... .... ..#. ...B
B A
Olympiad > Baltic Olympiad in Informatics > BOI 2008 1번