부저모으기

UVA10496 부저 모으기

카렐은 각각의 위치가 x, y 정수 좌표계로 세팅된 직사각형 좌표 시스템에서 행동하는 로봇이다. 카렐이 땅위에 떨어진 여러 부저들을 줍는 것을 도와줄 프로그램을 작성해야 한다. 이를 위해서, 각 부저가 위치한 곳으로 카렐을 이끌어야 한다. 카렐이 시작 지점으로부터 모든 부저들을 다 거치고 시작 지점으로 돌아오는 최단 경로의 길이를 구하는 프로그램을 작성하여라.

카렐은 x 축과 y 축을 따라서 이동할 수만 있다. (i,j)에서 인접한 위치 (i,j+1), (i,j-1), (i-1,j), (i+1,j) 로 이동하는 것은 비용 1이 사용된다.

카렐의 영역은 20 X 20 크기를 넘지 않으며, 주워야 할 부저는 최대 10 개다. 각 좌표는 (x, y) 쌍으로 구성된다.

입력

입력은 여러 테스트 데이터로 구성된다. 첫 번째 줄에는 테스트 데이터의 개수가 입력된다. 각 테스트 데이터의 첫 번째 줄에는 카렐의 영역 크기가 입력된다. 영역의 크기는 x 축의 크기와 y 축의 크기로 두 개의 정수로 입력된다. 다음 줄에는 카렐의 시작 지점을 나타내는 두 정수가 입력된다. 다음 줄에는 부저의 개수가 하나 입력된다. 다음 부저의 개수만큼 각 부저의 좌표가 정수 두 개로 한 줄에 하나씩 입력된다.

출력

각 테스트 마다 시작 지점으로부터 모든 부저를 다 줍고 다시 시작 지점으로 돌아오는 최단 경로를 한줄씩 출력해야 한다. 출력 형식은 출력 예제를 참고하여라.

입력 예제

1 10 10 1 1 4 2 3 5 5 9 4 6 5

출력 예제

The shortest path has length 24

풀이

 시작점이 양 끝에 붙는다는 점만 제외하면 중간에 부저간 이동은 완전 그래프에 속한다. 따라서, 이전 문제처럼 순열을 이용하여 다음 순열을 구하면서 처음과 마지막에 시작 지점을 덧붙여서 길이를 구한다

입력과 출력예제는 드래그를 하면 나옵니다..

소스파일 및 테이블 :

부저모으기 테이블.xls

부저모으기.cpp