IOI 1998 day2 2- 카멜롯(Camelot) > 문제은행 : 정보올림피아드&알고리즘




1678 : 카멜롯(Camelot)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
10 회   
시도횟수
32 회   

문제

 

수 세기 전, 아더왕과 원탁의 기사들은 새해 첫날엔 친목을 도모하기 위해 서로 만나곤 했다. 

우리는 그 당시, 그들이 친목을 도모하기 위해 

왕과 기사의 말이 서로 다른 칸에 아무렇게나 놓이는 한 1인용 보드 게임을 한 적이 있다고 생각한다.

보드는 8×8크기의 정사각형 배열이다.

 

 


 

왕은 한 번에 가로 세로 대각선으로 한 칸씩, 아래 그림에서 ●가 ○로 가는 방향으로 움직일 수 있다.

 

 


 

기사는 아래 그림에서 보다시피 한 번에 움직이는 범위가 체스의 기사와 같다.

 

 


 

물론 보드 영역 안에서만 이동이 가능하다. 한편, 게이머는 한 칸에 여러 말을 같이 놓을 수 있다. 

보드의 한 칸은 충분히 크기 때문에 한 칸에 아무리 많은 말을 동시에 놓아도 문제가 없다고 가정한다. 

이때 앞으로 끝까지 왕과 하나의 기사가 함께 이동할것인지, 기사가 따로 이동할것인지를 선택해야 한다. 

왕과 기사가 함께 이동할 경우 기사가 혼자 이동하는 방식으로 움직인다.

말들의 처음 상태를 읽고 모든 말을 한 위치로 모으는 데 최소 몇 번 말을 움직여야 하는지를 계산하는 프로그램을 작성하라.

 


입력형식

입력 파일에는 처음에 보드에 놓여 있는 말들의 위치가 기호화되어 들어 있다. 처음 알파벳은 가로 위치, 숫자는 세로 위치이다. 이것이 한 말의 좌표이다. 맨 처음 나온 위치는 왕의 좌표이며, 다음에 나오는 위치는 기사 말의 좌표이다. 좌표는 최대 64개까지 있을 수 있으며, 처음에는 모든 말의 위치가 서로 다르다. 예를 들어,

D4A3A8H1H8

이라고 하면 왕의 말은 D4의 위치에 있다. 기사 말은 네 개이며, 각각 A3, A8, H1, H8위치에 있는 것이다. 왕은 반드시 하나만 존재 하며, 기사의 개수는 최대 63개 이다.


출력형식

반드시 한 줄에 최소한의 움직임 횟수를 정수로 출력한다.


입력 예

D4A3A8H1H8

출력 예

10


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP