Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1996_3e2_rubiko_kubas.in

Rezultatų failas: lmio_1996_3e2_rubiko_kubas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Rubiko-kubas

Įsivaizduokite, kad turite Rubiko kubą, sudarytą iš n\\timesn\\timesn mažų kubelių. Po kubą landžioja nykštukas. Būdamas bet kurioje kubo vietoje (bet kuriame mažame kubelyje) jis gali pasiekti bet kurį kitą kubelį. Judėti jam leidžiama lygiagrečiai kuriai nors kubo briaunai. Vienu žingsniu jis gali pereiti tik į kurį nors gretimą kubelį.

Kiekvienas mažas kubelis turi tris koordinates (x,y,z). Koordinatės — natūralieji skaičiai iš intervalo [1,n]. Koordinačių pradžia yra bet kuri Rubiko kubo viršūnė, o x, y, z ašys sutampa su iš tos viršūnės išeinančiomis kubo briaunomis. Kubelio prie tos viršūnės koordinatės yra (1,1,1). Paėjus vieną žingsnį kuria nors kryptimi, vienetu padidėja (arba sumažėja) ir atitinkama tos krypties koordinatė.

Per kai kuriuos kubelius negalima pralįsti – jie yra kliūtys, kurias reikia aplenkti. Tokių kliūčių kubelių yra k.

Užduotis

Parašykite programą, kuri rastų trumpiausio kelio nuo kubelio A(x_1,y_1,z_1) iki kubelio B(x_2,y_2,z_2) ilgį, išreikštą žingsnių skaičiumi.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n,nurodantis Rubiko kubo dydį, antroje – A taško koordinatės x_1, y_1, z_1, trečioje – B taško koordinatės x_2, y_2, z_2, ketvirtoje – kliūčių skaičius k.

Po to eina k eilučių, kurių kiekvienoje yra trys skaičiai x, y, z – kliūčių koordinatės

Rezultatai

Rezultatas – žingsnių skaičius.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
3 
1 1 1 
3 3 3 
2
1 3 1 
2 3 1
 
6
 
Reikia nukeliauti iš vieno kubo kampo į priešingą. Yra tik dvi kliūtys, bet jos kelio neprailgina.

Ribojimai

n\\leq30