Šeštadieninė informatikos olimpiadininkų mokykla

Parašykite programą, kuri rastų ir pažymėtų trumpiausią kelią duotame labirinte.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas labirinto ilgis I ir plotis P. Sekančiose P eilučių pateikiamas pats labirintas. Jį sudaro simboliai . (taškas), # (grotelės), raidė s ir raidė f. Taškas reiškia, kad į šį langelį galima eiti, grotelės - kad negalima (siena). Raide s pažymėtas langelis yra pradinis, o raide f - galinis.

Labirinto ilgis ir plotis neviršija 200.

Rezultatai

Į rezultatų failą jūsų programa turi išvesti tą patį labirintą su pažymėtu keliu. Kelias pažymimas, pažymint langelius, kuriais reikia eiti, simboliu * (žvaigždute). Galimas ėjimas iš kiekvieno langelio yra tik aukštyn, žemyn, kairėn ir dešinėn.

Surastas kelias turi būti trumpiausias iš galimų (taigi turi būti mažiausias įmanomas skaičius žvaigždučių). Jei galimi keli trumpiausi keliai - jūsų programa turi pateikti bet kurį iš jų.

Galite tarti, kad kelias visada egzistuos.

Dėl aiškumo, žiūrėkite pavyzdžius.

Pavyzdžiai

5 6
s....
###.#
f#...
.#.#.
...#.
####.

s***.
###*#
f#**.
*#*#.
***#.
####.

10 7
####.....#
...###.#.#
.#.....#.#
s#####.#.f
.#...#.#.#
...#.....#
##########

####.....#
...###.#.#
.#.....#.#
s#####.#*f
*#***#.#*#
***#*****#
##########