15. detsember

Lennartil on täna töö juures jõulupidu, kuid kõikide sekelduste kõrvalt unustas ta totaalselt ära, et peab võtma sinna kaasa ühe kingituse, mis mõnele töökaaslasele välja loositakse. Õnneks tekkis Lennartil üks hea mõte ja viimasel hetkel enne kaubamaja sissepääsu sulgemist lipsas Lennart sisse.

See on üks suur kaubamaja ja Lennartil on vaja võimalikult kiirelt kõik vajalikud asjad kätte saada, nii et ta oli väga õnnelik kui avastas enda eest süsteemi, mis väljastab sulle kaardi, kuhu märgib kõigi vajalike poodide asukohad ja veel õiges järjekorras.

Nüüd palub Lennart sinu abi, et aitaksid tal välja arvutada kõige lühema teekonna läbi kõikide poodide, et ta saaks arvestada, kas ta ikka jõuab kõik poed läbi käia või peab ta mõne sel korral vahele jätma. Sisendi alguses on kirjutatud võtmesõna, mille kaardisüsteem Lennartile väljastas - iga täht tähistab ühte poodi. Samuti on lisanud süsteem kaardile Lennarti asukoha märgiga "-" ja kaubamaja väljapääsu märgiga "+". Poode peab läbima samas järjekorras, nagu nad sõnas esinevad. Järgnevatel ridadel on kaart, mille abil peab leidma kõige lühema teekonna läbi kõikide poodide. Liikuda saab külgnevaid poode pidi ehk diagonaalselt poodidele uksi pole tehtud. Kas leiad selle tee?

Näide:

KÜLMAV
-xxxA
xxxL+
KÜxxx
xxxVx
xxxxM

21

(Sammud tuleb seada ruudult (0,0) - K -> (2,0) - Ü -> (2,1) - L -> (1,3) - M -> (4,4) - A -> (0,4) - V -> (3,3) - +)