CSES - Labyrintti
  • 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 nn ja mm: labyrintin korkeus ja leveys.

Sitten syötteessä on nn riviä, joista jokaisella on mm 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

  • 1n,m10001 \le n,m \le 1000

Esimerkki

Syöte:

5 8
########
#.A#...#
#.##.#B#
#......#
########

Tuloste:

10-4
9
VAAOOOOOY