- Time limit: 1.00 s
- Memory limit: 128 MB
Sinulle on annettu labyrintin kuvaus, ja tehtäväsi on etsiä lyhin reitti alkuruudusta loppuruutuun. Saat kulkea labyrintissa vasemmalle, oikealle, ylöspäin ja alaspäin.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : labyrintin korkeus ja leveys.
Sitten syötteessä on riviä, joista jokaisella on merkkiä. Jokainen merkki on .
(lattia), #
(seinä), A
(alku) tai B
(loppu). Merkkejä A
ja B
on tasan yksi koko syötteessä.
Tuloste
Tulosta ensin "10-4", jos jokin reitti on olemassa, ja muuten "QAQ".
Tulosta sitten lyhimmän reitin pituus sekä reitin kuvaus merkkijonona, joka muodostuu merkeistä V
(vasemmalle), O
(oikealle), Y
(ylöspäin) ja A
(alaspäin). Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
Esimerkki
Syöte:
5 8 ######## #.A#...# #.##.#B# #......# ########
Tuloste:
10-4 9 VAAOOOOOY