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

문제

아주 오래 전에, 아더왕과 원탁의 기사들은 새 해를 맞이하여 한 곳에 모이곤 했었다. 이와 비슷하게, 체스판에 한 개의 왕과 여러 개의 나이트가 놓여 있고, 이들을 하나의 칸에 모으는 경우를 생각해 보자. 킹와 나이트의 움직임은 대략 다음과 같다.

단순히 킹과 나이트를 한 칸에 모으는 문제라면 쉽겠지만, 이 문제에서는 나이트가 킹을 자신의 말에 태우는 경우를 고려해야 한다. 즉, 킹과 한 개 이상의 나이트가 같은 칸에 놓여있을 때, 킹은 따로 움직일 수도 있고, 아니면 하나의 나이트가 타고 있는 말에 올라탈 수 있다. 킹이 말에 올라타는 것은 하나의 이동으로 세지 않으며, 올라 탄 이후에는 나이트와 똑같이 움직이게 된다. 한 번 말에 오른 킹은 다시 내릴 수는 없다.

나이트가 킹이 있는 곳까지 이동한 뒤에 킹을 태울 수도 있으며, 킹이 나이트가 있는 곳으로 이동하여 말에 오를 수도 있고, 킹과 나이트가 중간의 한 곳에서 만나서 말을 탈수도 있다.

킹과 나이트들의 초기 위치가 주어졌을 때, 이들을 한 칸에 모으기 위한 최소 이동 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기를 나타내는 두 정수 N(1≤N≤40), M(1≤M≤26)이 주어진다. N은 행의 개수, M은 열의 개수이다. 다음 줄에는 킹의 위치를 나타내는 문자 X와 수 Y가 주어진다. X는 알파벳 대문자로 표현되며, 열 번호를 의미한다. Y는 행 번호를 의미한다. 열 번호는 알파벳 A부터 차례대로 매겨진다. 다음 줄부터는 파일의 끝까지 나이트들의 위치가 주어진다. 나이트들의 위치 역시 킹의 위치와 같은 형식으로 주어진다. 파일의 끝은 두 개의 -1로 표현된다. 나이트는 0개일 수도 있고, 체스판을 가득 채울 수도 있다. 물론 같은 위치에는 한 개의 나이트만 있을 수 있다.

출력

첫째 줄에 킹과 나이트들을 한 칸에 모으기 위한 최소 이동 회수를 출력한다. 모이는 칸은 어느 곳이든 가능하다.

예제 입력

8 8
D 4
A 3 A 8 H 1 H 8
-1 -1

예제 출력

10

힌트

B5에 모이면 된다. 첫 번째 나이트는 A3 B5로 움직이며, 두 번째 나이트는 A8 C7 B5로 움직이며, 세 번째 나이트는 H1 G3 F5 D4(킹을 말에 태우고) B5로 움직이며, 네 번째 나이트는 H8-F7-D6-B5로 움직인다.