콜로니 정비 로봇

2xxx년, 인류는 지구를 떠나 우주 콜로니에 산다. 우주 방사선과 운석이 콜로니를 끊임없이 망가뜨리기 때문에 정비 로봇이 쉬지 않고 콜로니를 수리한다. 콜로니 위에서 로봇이 현재 위치에서 다음 수리 지점까지 이동하는 최단 거리를 구하는 프로그램을 작성하라.

콜로니는 폴리큐브로 나타낸다. 폴리큐브는 크기가 같은 정육면체 하나 이상을 면끼리 맞붙여 이어 놓은 입체다. 콜로니를 이루는 정육면체는 모두 이어져 있다. 즉 정육면체가 하나뿐인 콜로니를 빼면, 각 정육면체는 다른 정육면체와 면을 적어도 하나 맞대고 있다. 아래 그림은 콜로니의 예 두 가지다.

그림 2: 콜로니의 예

로봇은 폴리큐브의 표면, 즉 다른 정육면체와 맞닿지 않은 면 위에서만 움직인다. 콜로니의 구조 때문에 면의 경계를 넘는 이동은 다음 세 가지로 제한된다.

(a) 같은 정육면체의 인접한 두 면 사이를 넘는 이동 (b) 인접한 두 정육면체의 인접한 두 면 사이를 넘는 이동 (c) L자 모양의 안쪽을 따라가는 이동, 즉 공통으로 인접한 정육면체를 하나 갖는 두 정육면체의 인접한 두 면 사이를 넘는 이동

여기서 인접한 면은 모서리를 공유하는 두 면을 뜻하고, 인접한 정육면체는 면을 공유하는 두 정육면체를 뜻한다.

그림 3: 가능한 이동

정육면체는 모두 xyz 공간에 놓여 있고, 각 모서리는 x축, y축, z축 가운데 하나와 평행하다. 정육면체의 한 모서리 길이는 100이다.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n
x1 y1 z1
...
xn yn zn
sx sy sz dx dy dz

$n$은 콜로니를 이루는 정육면체의 개수다 ($1 \le n \le 16$). $(x_i, y_i, z_i)$는 $i$번째 정육면체의 중심 좌표이고, 각 좌표값은 정육면체의 한 모서리 길이인 100의 배수다. $(s_x, s_y, s_z)$는 로봇의 현재 위치, $(d_x, d_y, d_z)$는 다음 수리 지점이다. 두 점은 항상 서로 다르고, 둘 다 정육면체의 모서리 위에 있지 않다. 모든 좌표값은 $-2000$ 이상 $2000$ 이하의 정수다.

입력의 끝은 0 하나만 있는 줄로 나타낸다. 이 줄은 데이터셋이 아니므로 처리하지 않는다.

각 데이터셋마다 현재 위치에서 다음 수리 지점까지 가는 최단 경로의 길이를 한 줄에 출력한다. 소수점 아래 여섯째 자리까지 반올림해서 출력한다.

아래 그림은 예제 입력의 여섯 번째 데이터셋에서 로봇이 움직이는 모습을 보여준다.

그림 4: 여섯 번째 데이터셋에서 로봇의 이동