Šeštadieninė informatikos olimpiadininkų mokykla

Kažkur labirinte yra tortas ir jūs desperatiškai norite jį suvalgyti. Šio labirinto žemėlapis yra lentelė, sudaryta iš R eilučių ir C stulpelių. Kiekviename langelyje yra po vieną iš ženklų:

• # (grotelės) žymi labirinto sienos bloką,
• . (taškas) žymi atvirą langelį,
• S (didžioji raidė s) žymi atvirą langelį su jūsų dabartine pozicija,
• C (didžioji raidė c) žymi atvirą langelį, kuriame yra tortas.

Jūs galite vaikščioti tiktai atvirais langeliais ir pereiti į gretimus atvirus langelius, jeigu jie turi bendrą kraštinę. Be to, žemėlapyje vaizduojamą sritį iš visų pusių supa sienų blokai. Tam, kad greičiau pasiektumėte tortą, jūs įsigijote portalsvaidį iš Aperture Science™. Bet kuriuo laiko momentu juo galite sviesti portalą viena iš krypčių: aukštyn, kairėn, žemyn ir dešinėn. Kai portalas sviedžiamas kuria nors kryptimi, jis skrenda tol, kol atsitrenkia į pirmą sutiktą sienos bloką ir išsiskleidžia ant tos jo pusės, kuri yra atsisukusi į jus. Vienu metu gali egzistuoti daugiausiai du portalai. Jeigu du portalai jau išskleisti labirinte, vienas iš jų (jūsų pasirinkimu) bus pašalintas iškart, kai tik portalsvydis bus panaudotas dar kartą. Portalas, sviedžiamas ant jau išskleisto portalo, jį pakeis (t. y. ant kiekvienos sienos bloko pusės daugiausiai gali būti tik vienas portalas). Atkreipkite dėmesį, kad du portalai gali būti išskleisti ant skirtingų to paties sienos bloko pusių. Kai labirinte išskleisti du portalai, juos galima naudoti teleportacijai: jeigu stovite langelyje šalia portalo, galite į jį įeiti ir atsidurti atvirame langelyje šalia kito portalo. Šis veiksmas užtrunka lygiai tiek pat, kiek ir pereiti tarp gretimų langelių. Laikykite, kad portalų svaidymas neužima laiko, o perėjimas tarp gretimų langelių arba teleportacija tarp portalų užtrunka vieną laiko vienetą.

Užduotis

Duotam labirinto žemėlapiui su pažymėtomis jūsų ir torto pozicijomis apskaičiuokite trumpiausia laiką, per kurį galite pasiekti tortą.

Pradiniai duomenys

Pirmoje eilutėje yra du sveikieji skaičiai: žemėlapio eilučių skaičius R ir stulpelių skaičius C. Toliau R eilučių apibūdina žemėlapį. Kiekvienoje iš šių eilučių yra lygiai C ženklų: #, ., S arba C (kurių reikšmės apibrėžtos aukščiau). Garantuojama, kad ženklai S ir C žemėlapyje bus panaudoti po vieną kartą.

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių – kiek mažiausiai laiko vienetų užtrunka pasiekti tortą iš pradinės pozicijos.

Laikykite, kad iš jūsų pradinės pozicijos galima pasiekti tortą.

Ribojimai

.

Pavyzdžiai

4 4
.#.C
.#.#
....
S...

4