Šeštadieninė informatikos olimpiadininkų mokykla

Č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

1 10
*........X

9

1 3
*#X

-1

3 20
####################
#XZ.gMr.*.Rm.G.GG.z#
####################

45