Laiko ribojimas: 1s
Atminties ribojimas: 64MB
Duomenų failas: raktai.in
Rezultatų failas: raktai.out
Raktų užduotis
Čekijos technologijos universitetas yra gana senas. Jam jau virš 300 metų. Kai kurie universiteto pastatai yra taip pat seni. Judėjimas senuose pastatuose kartais gali būti keblus dėl ilgų keistų koridorių, kurie skyla ir jungiasi pačiose keisčiausiose vietose.
Dėl to kai kuriems pirmakursiams sunku rasti teisingą kelią į auditorijas. Taigi studentų sąjunga sukūrė žaidimą, kuris turėtų padėti studentams pasitikrinti savo orientavimosi sugebėjimus. Žaidimo tikslas yra rasti kelią iš labirinto. Jūsų užduotis - parašyti programą, kuri įveiktų šį žaidimą.
Labirintas yra 2 dimensijų tinklelis sudarytas iš kvadratėlių, kurie yra arba laisvi, arba juose yra siena. Kai kuriuose laisvuose kvadratėliuose yra raktai arba durys. Yra keturios raktų ir durų spalvos: mėlyna, raudona, geltona ir žalia. Kiekvienas raktas gali atrakinti tik tos pačios spalvos duris.
Galima judėti tarp gretimų kvadratėlių horizontaliai arba vertikaliai, bet ne įstrižai. Negalima eiti į kvadratėlį, kuriame yra siena. Į kvadratėlį, kuriame yra durys, galima įeiti tik, jei anksčiau buvo įeita į kvadratėlį su atitinkamos spalvos raktu.
Pradiniai duomenys
Pirmoje eilutėje yra labirinto dydis - du sveiki skaičiai R ir C (). Tolesnėse R eilučių yra po C simbolių. Galimi simboliai ir jų reikšmės:
- # - siena
- . - tuščias kvadratėlis
- * - pradinė pozicija
- M R G Z - atitinkamai mėlynos, raudonos, geltonos arba žalios durys
- m r g z - atitinkamai mėlynas, raudonas, geltonas arba žalias raktas
- X - išėjimas
Pradinė pozicija bus lygiai viena, išėjimų - bet koks kiekis. Kiekvienos spalvos durų ir raktų irgi gali būti bet kiek.
Rezultatai
Vienintelėje eilutėje rašykite vieną skaičių - mažiausią ėjimų kiekį, reikalingą norint pasiekti išėjimą. Jei išėjimo pasiekti neįmanoma, rašykite -1. Ėjimu laikomas perėjimas tarp gretimų kvadratėlių; rakto paėmimas ar durų atrakinimas neužtrunka ėjimo.
Pavyzdys
Duomenys | Rezultatai |
---|---|
1 10 *........X |
9 |
1 3 *#X |
-1 |
3 20 #################### #XZ.gMr.*.Rm.G.GG.z# #################### |
45 |