Annettuna on suunnistuskartta, jossa on seuraavia symboleja:

• .: polkuruutu
• #: esteruutu
• S: lähtöruutu
• E: maaliruutu
• 1–9: rasti

Voit liikkua kartalla joka askeleella viereiseen ruutuun ylös, alas, vasemmalle tai oikealle. Et saa liikkua esteruutuun.

Tehtäväsi on etsiä lyhin reitti lähtöruudusta maaliruutuun, jossa käyt kaikki rastit läpi järjestyksessä. Samalla numerolla saattaa olla useita rasteja, jolloin voit valita minkä tahansa niistä.

Rastiruudussa käyminen ei haittaa, vaikka sen numero ei olisi järjestyksessä seuraavana.

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua n, m ja k: kartan korkeus ja leveys sekä rastien määrä.

Seuraavat n riviä kuvaavat kartan. Symbolit S ja E esiintyvät tasan kerran kartassa.

Tuloste

Tulosta lyhin reitin pituus. Jos reitti ei ole mahdollinen, tulosta -1.

Esimerkki 1

Syöte:

4 7 3
#1.##E.
3...##3
.S#.##.
.2#1..1

Tuloste:

18

Selitys: Voit kulkea 2 askelta ylös (rasti 1 käyty), 3 askelta alas (rasti 2 käyty), 2 askelta ylös, 2 askelta oikealle, 2 askelta alas, 3 askelta oikealle, 3 askelta ylös (rasti 3 käyty) ja 1 askeleen vasemmalle.

Esimerkki 2

Syöte:

4 7 3
#1.##E.
3...##3
.S#.##.
..#1..1

Tuloste:

-1

Selitys: Rasti 2 puuttuu, minkä takia mitään reittiä ei ole olemassa.

Osatehtävä 1 (31 pistettä)

• 1 \le n, m \le 500
• k = 0

Osatehtävä 2 (12 pistettä)

• 1 \le n, m \le 500
• 0 \le k \le 9
• Jokainen rasti esiintyy enintään kerran

Osatehtävä 3 (57 pistettä)

• 1 \le n, m \le 500
• 0 \le k \le 9