Kubik Koloniyalar
AD 3456-cı ildə yer üzündə yüz milyardlarla insanın sülh içində yaşaması üçün yer kifayət qədər böyük deyil. Kubiklər ilə Ulduzlararası Kolonizasiya Layihəsi (ICPC) bu problemi həll etmək üçün yer üzündəki insanları kosmos koloniyalarına köçürməyi hədəfləyir. ICPC hökumətlərdən maliyyə dəstəyi alaraq, prefabrik kubik bloklardan istifadə edərək kosmos koloniyalarını sürətli və ucuz şəkildə istehsal edir.
Ən böyük koloniya Rubik kubuna bənzəyir və 3×3×3 kubik bloklardan ibarətdir (Şəkil 1A). Daha kiçik koloniyalar isə bu böyük koloniyadakı bəzi blokların əskik olduğu hallardır.
Koloniya istehsalında çoxlu kubik bloklar istifadə edərkən, bir blokla başlayırıq və növbəti bloku mövcud bloklara üzləri tam uyğun gələcək şəkildə yapışdırırıq. Toxunan hər üz cütü yapışdırılır.
Şəkil 1: Ən böyük koloniya və daha kiçik bir koloniyanın nümunəsi
Lakin, ilk buraxılışdan dərhal əvvəl koloniyalarla bağlı bir dizayn qüsuru aşkar etdik. Hər bir koloniyanın səthindəki iki nöqtəni birləşdirmək üçün bir kabel əlavə etməliyik, lakin prefabrik blokların içini qısa müddətdə dəyişdirə bilmirik. Buna görə də hər bir koloniyanın səthinə kabel əlavə etməyə qərar verdik. Kabelin bir hissəsi səthdə deyilsə, buraxılış zamanı kəsilər, buna görə də bütün kabeli səthə qoymalıyıq. Büdcə məhdudiyyətləri səbəbindən kabellərin uzunluqlarını minimuma endirmək istəyirik. Şəkil 1B-dəki kəsik xətt belə bir nümunədir. Verilən koloniyanın formasına və səthindəki iki nöqtəyə əsasən, həmin koloniya üçün mümkün olan ən qısa kabelin uzunluğunu hesablayan bir proqram yazın.
Giriş verilənləri
Giriş bir sıra datasetlərdən ibarətdir. Hər bir dataset bir koloniyanı və koloniyanın nöqtə cütünü aşağıdakı formatda təsvir edir.
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) və (x_2, y_2, z_2) koloniyanın səthindəki iki fərqli nöqtədir, burada x_1, x_2, y_1, y_2, z_1, z_2 tam ədədlərdir və 0 ≤ x_1, x_2, y_1, y_2, z_1, z_2 ≤ 3 şərtini ödəyir. b_{i,j,k} '#'-dır, əgər (i, j, k) və (i+1, j+1, k+1) iki diaqonal zirvəsi olan bir kubik blok varsa, və b_{i,j,k} '.'-dır, əgər blok yoxdursa. Şəkil 1A nümunə girişindəki ilk datasetə, Şəkil 1B isə ikinciyə uyğun gəlir. Kabel iki blok yalnız zirvələri və ya kənarları ilə toxunduqda sıfır eni olan boşluqdan keçə bilər. Şəkil 2A-da, nümunə girişindəki üçüncü dataset, ən qısa kabel A (0, 0, 2) nöqtəsindən B (2, 2, 2) nöqtəsinə gedir və (1, 1, 2) nöqtəsindən keçir, bu nöqtə altı blok tərəfindən paylaşılır. Eyni şəkildə, Şəkil 2B-də (nümunə girişindəki dördüncü dataset) ən qısa kabel bir-birinə birbaşa yapışdırılmayan iki blok arasındakı boşluqdan keçir. İki blok yalnız bir zirvəni paylaşdıqda, zirvə vasitəsilə kabel yerləşdirə bilərsiniz (Şəkil 2C, nümunə girişindəki beşinci dataset).
Bütün 3×3×3 kubiklərdən ibarət olan, lakin mərkəz kubu olmayan bir koloniya olmadığını qəbul edə bilərsiniz.
Altı sıfır girişin sonunu bildirir.
Şəkil 2: Kəsik xətlər ən qısa kabellərdir. Bəzi bloklar təsvir üçün qismən şəffaf göstərilmişdir.
Çıxış verilənləri
Hər bir dataset üçün, verilmiş iki nöqtəni birləşdirən ən qısa kabelin uzunluğunu ehtiva edən bir sətir çıxarın. 0.0001-dən az səhvləri qəbul edirik. Verilmiş iki nöqtənin kabel vasitəsilə birləşdirilə biləcəyini qəbul edə bilərsiniz.