Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: pozemis.in

Rezultatų failas: pozemis.out

Jei norite pateikti savo sprendimą - prisijunkite.

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 (1\\leL,R,C\\le30) - 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