Кубические колонии
В 3456 году нашей эры Земля стала слишком тесной для сотен миллиардов людей, и жить в мире стало невозможно. Проект межзвездной колонизации с кубами (ICPC) — это инициатива, направленная на переселение людей с Земли в космические колонии для улучшения ситуации. ICPC получил финансирование от правительств и быстро и экономично создал космические колонии из сборных кубических блоков.
Самая большая колония напоминает кубик Рубика и состоит из 3×3×3 кубических блоков (Рисунок 1A). Меньшие колонии представляют собой версии этой колонии с отсутствующими блоками.
При создании колонии из кубических блоков мы начинаем с одного блока и постепенно добавляем новые, приклеивая их к уже существующим так, чтобы их грани совпадали. Каждая пара соприкасающихся граней склеивается.
Рисунок 1: Пример самой большой колонии и меньшей колонии
Однако, незадолго до первого запуска, был обнаружен конструктивный недостаток в колониях. Нам необходимо провести кабель для соединения двух точек на поверхности каждой колонии, но мы не можем быстро изменить внутреннюю часть сборных блоков. Поэтому мы решили проложить кабель по поверхности колонии. Если часть кабеля не будет находиться на поверхности, она будет срезана во время запуска, поэтому весь кабель должен быть размещен на поверхности. Мы стремимся минимизировать длину кабелей из-за ограниченного бюджета. Пунктирная линия на Рисунке 1B иллюстрирует такой пример. Напишите программу, которая, зная форму колонии и пару точек на ее поверхности, вычисляет длину самого короткого возможного кабеля для этой колонии.
Входные данные
Входные данные содержат несколько наборов данных. Каждый набор описывает одну колонию и пару точек для этой колонии в следующем формате.
x_1 y_1 z_1 x_2 y_2 z_2
b_{0,0,0} b_{1,0,0} b_{2,0,0}
b_{0,1,0} b_{1,1,0} b_{2,1,0}
b_{0,2,0} b_{1,2,0} b_{2,2,0}
b_{0,0,1} b_{1,0,1} b_{2,0,1}
b_{0,1,1} b_{1,1,1} b_{2,1,1}
b_{0,2,1} b_{1,2,1} b_{2,2,1}
b_{0,0,2} b_{1,0,2} b_{2,0,2}
b_{0,1,2} b_{1,1,2} b_{2,1,2}
b_{0,2,2} b_{1,2,2} b_{2,2,2}
(x_1, y_1, z_1) и (x_2, y_2, z_2) — это две различные точки на поверхности колонии, где x_1, x_2, y_1, y_2, z_1, z_2 — целые числа, удовлетворяющие 0 ≤ x_1, x_2, y_1, y_2, z_1, z_2 ≤ 3. b_{i,j,k} — это '#', если существует кубический блок с диагональными вершинами (i, j, k) и (i+1, j+1, k+1), и '.', если блока нет. Рисунок 1A соответствует первому набору данных в примере входных данных, а Рисунок 1B — второму. Кабель может проходить через зазор нулевой ширины между блоками, если они касаются только вершинами или ребрами. На Рисунке 2A, который является третьим набором данных, самый короткий кабель идет от точки A (0, 0, 2) до точки B (2, 2, 2), проходя через (1, 1, 2), которая разделяется шестью блоками. Аналогично, на Рисунке 2B (четвертый набор данных), самый короткий кабель проходит через зазор между двумя блоками, не склеенными напрямую. Когда два блока разделяют только одну вершину, кабель может пройти через вершину (Рисунок 2C, пятый набор данных).
Вы можете предположить, что не существует колонии, состоящей из всех 3×3×3 кубов, кроме центрального куба.
Шесть нулей завершают ввод.
Рисунок 2: Пунктирные линии — это самые короткие кабели. Некоторые блоки показаны частично прозрачными для иллюстрации.
Выходные данные
Для каждого набора данных выведите строку, содержащую длину самого короткого кабеля, который соединяет две заданные точки. Погрешность должна быть менее 0.0001. Вы можете быть уверены, что данные точки могут быть соединены кабелем.