Code Submission Evaluation System Login

IOI-leiri 2016

Labyrintti


Task | Statistics


CSES - LabyrinttiCSES - Labyrintti

Time limit:1.00 s Memory limit:128 MB

Sinulle on annettu kuvaus labyrintista, joka muodostuu seuraavista ruuduista:
Kaikki labyrintin reunaruudut ovat seinää. Voit liikkua labyrintissa pysty- ja vaakasuuntaisesti. Ovesta voi kulkea vain, jos sinulla on sitä vastaava avain. Voit pitää hallussasi rajattomasti avaimia samaan aikaan.

Mikä on pienin määrä askelia, joilla pääset alkukohdasta loppukohtaan?

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ä. Nämä rivit kuvaavat labyrintin sisällön.

Tuloste

Tulosta yksi kokonaisluku: pienin askelten määrä.

Rajat
Esimerkki

Syöte:
8 10
##########
#...A.#$.#
#.###.##B#
#.#a#c##.#
#.#.#.#..#
#.#.#.#.##
#.@.#...b#
##########


Tuloste:
34