카렐은 (x,y) 좌표축을 돌아다니는 로봇이다. 좌표 축에 놓여져 있는 호출기를 모두 주우려고 한다.
이럴 위해서 카렐은 호출기가 있는 장소로 직선 코스 움직인다. 카렐이 있는 현재 위치에서 모든 호출기를 줍고 현재 위치로 돌아오는 최단거리 구하는 것이 문제이다.
카렐은 x,y 축을 따라서만 움직일 수있고 대각선으로 움직이지는 못한다. 즉 (i,j) 위치에 있다면 (i,j+1) , (i,j-1) , (i-1,j), (i+1,j) 로만 움직일 수 있다.
좌표값은 최대 20*20 을 넘지 않고 많아야 10 개의 호출기가 있다. 좌표값은 1 이상 주어지는 좌표값 범위안에 존재한다.
입력 10 10 1 1 4 2 3 5 5 9 4 6 5 출력 The shortest path has length 24
출처:Svenskt Masterskap i Programmering/Norgesmesterskapet 2002