D1 - Dungeon Arcade

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Arkádové plošinovky boli niekedy veľmi populárne. Určite si spomeniete na hru Prince of Persia, ktorá sa vyznačovala skvelou grafikou a veľmi realistickou animáciou alebo priekopnícky Donkey Kong. Ale ešte pred dobami grafických hier sa hrávali hry čisto textové. V tej dobe naprogramoval jeden študent len tak, pre svoje vlastné potešenie, hru s názvom Dungeon Arcade. Išlo o veľmi jednoduchú hru, v ktorej bolo úlohou hráča dostať sa od jedného vchodu k druhému. Pritom mohol chodiť alebo sa šplhať po rebríkoch. Samozrejme, chôdza a šplhanie sa zabrali hráčovi rozličný čas. Keď bola hra skoro hotová, dal ju nemenovaný študent niekoľkým svojim kamarátom na testovanie. Tí boli hrou nadšení a pretekali sa v tom, kto dokáže jednotlivé levely prejsť za čo najkratší čas. Takto si viedli rebríček. Problém bol, že po istom čase sa časy pre jednotlivé levely ustálili na istých hodnotách a začalo sa zdať, že sa už nedajú vylepšiť. Nikto si ale nebol istý. Preto sa daný študent rozhodol napísať analyzátor levelov, ktorý by vedel najkratší čas, potrebný na prejdenie levelu, vypočítať. Žiaľ, jeho algoritmické znalosti boli dosť chudobé a tak sa mu to v tom čase nepodarilo. Aj jeho spolužiaci si čoskoro našli inú zábavu a táto neznáma hra zapadla prachom, až kým sa, spolu so všetkými záznamami najlepších časov, neobjavila v archíve nemenovanej univerzity.

Úloha

Pre každú mapu (level) zistite, koľko najmenej času je potrebné na jej úspešné absolvovanie, to znamená, za najmenej koľko sekúnd sa dá prejsť od jedného vchodu k druhému. Na samotnej mape sa nachádzajú tieto druhy políčok:

Znak "." (bodka) je prázdne miesto.
Znak "#" (záhradka) znázorňuje plnú stenu. Nad týmto políčkom môže hráč stáť a chodiť po jeho povrchu. Prejdenie po jednom takomto políčku zaberie 3 sekundy.
Znak "|" (pajpa) znázorňuje rebrík. Ak stojí hráč na políčku s rebríkom, môže vyliezť vyššie, ak nad ním je tiež políčko s rebríkom alebo východ, alebo nižšie, ak je políčko s rebríkom alebo východ pod ním. Do strán sa môže pohnúť, len ak je vedľa rebrík, východ, alebo bude stáť na plnom políčku. Pohyb cez toto políčko zaberie presne 5 sekúnd, či už ide o horizontálny alebo vertikálny pohyb.
Znak "*" (hviezdička) je vchod alebo východ. Dá sa z neho pohnúť hore alebo dole, ak je nad ním, resp. pod ním rebrík. Do strán sa z neho môže hráč pohnúť, len ak je vedľa rebrík, východ, alebo bude stáť na plnom políčku. Pohyb z tohoto políčka nezaberie žiaden čas.

Hráč nemôže skákať, spadnúť ani vysieť z rebríka a tak zoskočiť na nohy. Môže len chodiť alebo preliezať po rebríku na susediace políčka.

Vstup D1

Prvý riadok vstupu obsahuje dve prirodzené čísla 1 ≤ M,N ≤ 50, kde M je počet riadkov mapy a N je počet stĺpcov. Ďalej nasleduje M riadkov po N znakov, pričom znaky sú len "#" (záhradka), "|" (pajpa), "." (bodka) a "*" (hviezdička). Hviezdičky sa nachádzajú na mape práve dve.

Vstup D2

Prvý riadok vstupu obsahuje dve prirodzené čísla 1 ≤ M,N ≤ 50, kde M je počet riadkov mapy a N je počet stĺpcov. Ďalej nasleduje M riadkov po N znakov, pričom znaky sú len "|" (pajpa), "." (bodka) a "*" (hviezdička). Hviezdičky sa nachádzajú na mape práve dve.

Výstup

Ak existuje cesta medzi dvoma hviezdičkami, vypíšte počet sekúnd, ktoré trvá najkratšia možná cesta. Ak neexistuje, vypíšte reťazec "neda sa" (bez úvodzoviek).

Príklad 1

Vstup:

10 10
.|........
|*|||||||.
.|..|...|.
|.|..|..|.
.||||||||.
.||.......
.||||||||.
|....|..|.
|*|||||||.
||........

Výstup:

Vysvetlenie:

Vo verzii D1 sú len rebríky, ktorých prelezenie ľubovoľným smerom zaberie presne 5 sekúnd. Najkratšia cesta je:

.|........
|*|||||||.
.|..|...|.
|.|..|..|.
.||||||||.
.||.......
.||||||||.
|....|..|.
|*|||||||.
||........

Po ceste musí hráč preliezť 26 rebríkov, takže potrebuje čas 130 sekúnd.

Príklad 2

Vstup:

10 10
.|........
|*|||||||.
#|##|###|.
|.|..|..|.
|.|.....|.
|.|######.
..|..||||.
|####|..|.
|*.|.||||.
|.#.#.....

Výstup:

Vysvetlenie:

Vo verzii D2 sú už aj steny. Najkratšia cesta je:

.|........
|*|||||||.
#|##|###|.
|.|..|..|.
|.|.....|.
|.|######.
..|..||||.
|####|..|.
|*.|.||||.
|.#.#.....

Po ceste musí prejsť po 16 povrchoch a preliezť 10 rebríkov. Všimnite si, že keď hráč zlezie po rebríku a pod ním je podlaha, oplatí sa mu viac ísť po nohách ako použiť rebrík pre horizontálny pohyb.

UPJŠ ŠVK 2010