카멜롯

체스판에 왕 하나와 여러 나이트가 놓여 있다. 왕과 모든 나이트를 같은 칸에 모으는 데 필요한 최소 이동 횟수를 구해야 한다.

왕은 한 번에 주변 8칸 중 하나로 이동할 수 있다. 나이트는 체스의 나이트처럼 한 방향으로 2칸, 그와 직각인 방향으로 1칸 이동한다.

왕과 하나 이상의 나이트가 같은 칸에 있으면, 왕은 그중 한 나이트의 말에 올라탈 수 있다. 올라타는 행동은 이동 횟수에 포함하지 않는다. 말에 오른 뒤에는 그 나이트와 함께 나이트처럼 이동하며, 다시 내릴 수 없다.

나이트가 왕이 있는 칸으로 이동해 왕을 태울 수도 있고, 왕이 나이트가 있는 칸으로 이동해 탈 수도 있다. 또는 왕과 나이트가 중간의 어떤 칸에서 만나 왕이 말에 오를 수도 있다.

킹과 나이트들의 초기 위치가 주어질 때, 모두를 한 칸에 모으기 위한 최소 이동 횟수를 출력하라.

첫째 줄에 체스판의 크기를 나타내는 두 정수 N과 M이 주어진다. N은 행의 개수이고 M은 열의 개수이다. 1 <= N <= 40, 1 <= M <= 26이다.

다음 줄에는 왕의 위치를 나타내는 문자 X와 정수 Y가 주어진다. X는 열 번호를 뜻하며 A부터 차례대로 매겨진 대문자 알파벳이다. Y는 행 번호이다.

그다음부터는 입력이 끝날 때까지 나이트들의 위치가 왕의 위치와 같은 형식으로 주어진다. 나이트 목록은 두 토큰 -1 -1로 끝난다.

나이트는 0개일 수도 있고, 체스판을 가득 채울 수도 있다. 같은 칸에 두 나이트가 놓이는 경우는 없다.

왕과 모든 나이트를 한 칸에 모으기 위한 최소 이동 횟수를 출력한다. 모이는 칸은 체스판 위의 어느 칸이어도 된다.

왕이 D4에 있고 나이트가 A3, A8, H1, H8에 있다면 B5에 모일 수 있다. 첫 번째 나이트는 A3 -> B5로, 두 번째 나이트는 A8 -> C7 -> B5로, 세 번째 나이트는 H1 -> G3 -> F5 -> D4에서 왕을 태운 뒤 B5로, 네 번째 나이트는 H8 -> F7 -> D6 -> B5로 이동한다.