Кубічні Колонії
У 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), і b_{i,j,k} дорівнює '.', якщо блоку немає. Рисунок 1A відповідає першому набору даних у прикладі вводу, тоді як Рисунок 1B відповідає другому. Кабель може проходити через нульову ширину зазору між двома блоками, якщо вони торкаються лише своїми вершинами або ребрами. На Рисунку 2A, який є третім набором даних у прикладі вводу, найкоротший кабель йде від точки A (0, 0, 2) до точки B (2, 2, 2), проходячи через (1, 1, 2), яка є спільною для шести блоків. Аналогічно, на Рисунку 2B (четвертий набір даних у прикладі вводу), найкоротший кабель проходить через зазор між двома блоками, які не склеєні безпосередньо. Коли два блоки мають лише одну спільну вершину, ви можете прокласти кабель через цю вершину (Рисунок 2C, п'ятий набір даних у прикладі вводу).
Ви можете припустити, що не існує колонії, що складається з усіх 3×3×3 кубів, крім центрального куба.
Шість нулів завершують ввід.
Рисунок 2: Пунктирні лінії - це найкоротші кабелі. Деякі блоки показані частково прозорими для ілюстрації.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить довжину найкоротшого кабелю, який з'єднує дві задані точки. Ми приймаємо похибки менше 0.0001. Ви можете припустити, що задані дві точки можуть бути з'єднані кабелем.