시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 22 2 2 12.500%

문제

드록바와 셰브첸코가 첼시에서 같이 훈련하던 옛날 옛적 어느날 두 선수는 훈련에 지쳐 다음과 같은 게임을 하며 쉬기로 한다.

편의상 두 플레이어를 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

힌트

첫 번째 테스트 케이스의 경우인데 A가 어떤 방향으로 움직이던 B가 따라가게 된다면 A가 3칸을 움직이고 B가 3칸째 움직이게 될 때 A의 위치와 겹칠 수 있고 그때 B가 한 번의 추가 움직임을 허용 받아 더 먼저 상대의 시작장소로 갈 수 있다. 이는 두 번째 테스트 케이스의 경우인데 이 경우 B가 어떻게 가던 A가 피해간다면 만나지 않을 수 있고 서로 만나지 않는다면 먼저 시작한 A가 승리할 수 있다.

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 2번

  • 문제를 번역한 사람: author4