Laiko ribojimas: 1s
Atminties ribojimas: 64MB
Duomenų failas: pozemis.in
Rezultatų failas: pozemis.out
Požemis
Esate įkalintas trijų dimensijų požemyje ir jums reikia surasti greičiausią kelią lauk! Požemis sudarytas iš vienetinių kubų, kurie gali būti tušti arba užpildyti akmenimis. Galima paeiti į šiaurę, į pietus, į rytus, į vakarus, į viršų ar į apačią per vieną kubą ir tai užtrunka vieną minutę. Įstrižai judėti negalima. Požemis iš visų pusių apsuptas akmenimis.
Ar įmanoma pasprukti? Jei taip, kiek mažiausiai tai užtruks?
Pradiniai duomenys
Pirmoje eilutėje yra trys sveikieji skaičiai L, R, C (
) - požemio matmenys. Požemį sudaro L aukštų, kurių kiekvienas turi R eilučių ir C stulpelių. Toliau pateiktas pats požemis - L blokų po R eilučių iš C simbolių; kiekvienas blokas atitinka vieną aukštą. Požemio žemėlapyje '#' žymi akmenis, '.' - tuščią vietą, 'S' - pradžios tašką, 'E' - pabaigos tašką. Simboliai 'S' ir 'E' plane bus lygiai po vieną kartą.
Rezultatai
Viena eilutė su vienu skaičium, reiškiančiu mažiausią laiko tarpą, reikalingą pasprukti iš požemio. Jei pasprukti neįmanoma, rašykite -1.
Pavyzdys
| Duomenys | Rezultatai |
|---|---|
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E |
11 |