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

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

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

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

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

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

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

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

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

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

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

카멜롯(Camelot) timer 1s memory 128MB

카멜롯(Camelot) 1s 128MB