2001년 가을학기 문제해결기법 - 문제 10

상자위의 개미

가로, 세로, 높이가 각각 a, b, c인 직육면체 모양의 상자가 있다. 이 상자의 표면에는 개미 두 마리가 있다. 개미 한 마리가 다른 개미가 있는 위치로 이동하려고 한다. 당신이 할 일은 이 개미에게 가장 빠른 길을 찾아서 알려주는 것이다. 개미는 상자 속으로 들어갈 수 없고, 또 바닥에 닿아있는 면으로는 이동할 수 없다.

개미의 위치를 말하기 위해서 이 상자가 다음과 같이 x,y,z-공간에 있다고 가정한다. 박스의 한 꼭지점의 좌표는 (0,0,0)이고 이 꼭지점과 가장 먼 꼭지점의 좌표는 (a,b,c)이다. 즉, 박스의 꼭지점의 좌표는 다음과 같다: (0,0,0), (a,0,0), (a,b,0), (0,b,0), (0,0,c), (a,0,c), (a,b,c), (0,b,c).

프로그램명은 box.cpp(box.c)라고 하고 실행 파일명은 box.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 상자의 가로, 세로, 높이가 실수로 주어진다. 둘째 줄에 개미의 현재 위치의 좌표가 주어지고, 셋째 줄에 개미의 최종 위치가 주어진다. 개미의 위치는 x 좌표, y 좌표, z좌표 순서로 주어진다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 최단 경로의 길이를 출력한다.

입력과 출력의 예

INPUT.TXT

2.0 3.0 4.0

1.0 0.0 3.0

1.0 3.0 3.0

OUTPUT.TXT

5.0