체커

한 번의 연속 점프로 모든 백 말을 잡는 흑 말을 찾고 없거나 여러 개면 None이나 Multiple을 출력합니다.

보통5백트래킹DFS시뮬레이션아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

체커는 n×nn \times n 크기의 체커판에서 두는 게임이다. nn은 보통 8, 10, 12이지만 이 문제에서는 2 이상 26 이하이다. 판의 칸은 빨간색과 검은색으로 칠해져 있고, 모든 말은 검은 칸 위에서만 움직인다. 두 진영을 검은색과 흰색이라고 부르고, 각 진영의 말도 같은 색이다. 열은 왼쪽부터 a로 시작해 알파벳 순서로 매기고, 행은 맨 아래부터 1, 2, ..., nn으로 번호를 매긴다. 각 칸은 열 문자 뒤에 행 번호를 붙여서 나타낸다. 예를 들어 c6, z10, b26처럼 쓴다. 아래 그림은 판 두 개를 보여준다. 열 번호를 알아보기 쉽도록 표시를 덧붙였다.

말은 상대 색 말을 대각선으로 뛰어넘어 잡을 수 있고, 잡힌 말은 판에서 사라진다. 뛰어넘으려면 넘을 말이 뛰는 말과 대각선으로 맞닿아 있어야 하고, 그 말 바로 너머의 칸이 비어 있어야 한다. 한 번 잡은 뒤에도 잡을 말이 남아 있으면, 같은 말이 더 뛸 수 없을 때까지 계속 뛰어넘어 잡을 수 있다.

예를 들어 왼쪽 판에서 b6의 검은 말은 한 번의 수로 흰 말 두 개를 모두 잡는다. 먼저 c5의 흰 말을 뛰어넘어 d4로 가고, 이어서 e5의 흰 말을 뛰어넘어 f6에 내려앉는다. 오른쪽 판에서는 어떤 검은 말도 흰 말을 뛰어넘지 못한다.

지금은 검은색이 둘 차례이다. 체커판이 주어질 때, 검은색이 한 번의 수로 흰 말을 모두 잡을 수 있는지 판단하라.

입력

첫째 줄에 판의 크기 nn이 주어진다 (2n262 \le n \le 26). 다음 nn개의 줄에 판의 상태가 한 줄에 nn글자씩 주어진다. 이 중 첫 줄이 맨 위인 nn번 행이고, 마지막 줄이 1번 행이다. 어떤 말도 놓일 수 없는 빨간 칸은 .이다. 말이 없는 검은 칸은 _, 검은 말은 B, 흰 말은 W이다.

주어지는 판에는 검은 말이 적어도 하나, 흰 말이 적어도 하나 있다. 또한 판은 항상 올바른 형태이다. 빨간 칸에 놓인 말은 없고, 칸의 색도 규칙에 맞게 칠해져 있다.

출력

한 번의 수로 흰 말을 모두 잡을 수 있는 검은 말의 위치를 한 줄에 출력한다. 그런 검은 말이 여러 개이면 Multiple을 출력한다. 그런 검은 말이 하나도 없으면 None을 출력한다.