Code Submission Evaluation System Login

Datatähti-valmennus

Labyrintti


Task | Statistics


CSES - Labyrintti

Time limit:1.00 s Memory limit:128 MB

Sinulle on annettu labyrintin kuvaus, ja tehtäväsi on etsiä reitti alkuruudusta loppuruutuun. Saat kulkea labyrintissa vasemmalle, oikealle, ylöspäin ja alaspäin.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: labyrintin korkeus ja leveys.

Sitten syötteessä on $n$ riviä, joista jokaisella on $m$ 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