Matfyzák v platformovke

Zadanie zápočtového testu, 20.1.2012

Matfyzák sa jedného dňa ocitol v počítačovej hre - platformovke. Platformovka to bola jednoduchá, pozostávala len z jednej 2D obrazovky a niekoľkých plošiniek na ktorých môže Matfyzák stáť. Okrem Matfyzáka sa v platformovke nachádza ešte jeden východ. Aby sa Matfyzák z platformovky dostal von, musí prejsť až k východu. (To, ako sa Matfyzák do platformovky dostal, a prečo ho cesta k východu oslobodí, je síce určite zaujímavý príbeh, pre potreby zadania úlohy však úplne nepodstatné. Iste sa už rýchlo chcete pustiť do programovania, tak príbeh odložím na inokedy.)

Obrazovka má tvar obdĺžnika NxM políčok. Každé políčko je buďto voľné, alebo je zabrané plošinkou. Na jednom voľnom políčku sa nachádza Matfyzák a na inom východ. Matfyzák sa môže po plošinkách pohybovať, a to na ľubovoľné voľné políčko z ôsmich susedných, aj diagonálne. Ako každý matfyzák je veľmi šikovný, a dokáže aj skákať, a to až o tri políčka naraz. Východ sa po plošinkách nepohybuje.

Fyzikálne zákony samozrejme platia aj na Matfyzáka, a teda ak skončí pohyb alebo skok vo vzduchu, spadne priamo dole až kým nedopadne na najbližšiu plošinku. Vypadnutie alebo vykročenie z obrazovky je pre Matfyzáka smrteľné, tak to neskúšajte. A to platí aj keď sa to stane v priebehu skoku, ktorý by inak skončil na obrazovke.

No a pretože Matfyzák je matfyzák, nepohne sa ani o krok kým nenájde najrýchlejšiu cestu k východu. Krok o jedno políčko trvá jednu sekundu, a skok trvá toľko sekúnd, koľko políčok sa preskakuje. Vy musíte Matfyzákovi pomôcť najrýchlejšiu cestu nájsť.

Popis vstupu programu

Na prvom riadku vstupu sú dve celé čísla N a M, popisujúce rozmery obrazovky. Môžete predpokladať limity 0 < N, M < 50. Nasleduje N riadkov, každý práve M znakov dlhý, zobrazujúcich obrazovku platformovky. Voľné políčka sú označené znakom ".", plošinky znakom "#". Počiatočná pozícia Matfyzáka je označená "M" a východ "V". Môžte predpokladať že Matfyzák aj východ na začiatku stoja na plošinke, a že na obrazovke sa nachádza práve jeden Matfyzák a práve jeden východ.

Teda vstup môže vyzerať napríklad takto:

4 12
........#V..
....#...###.
M..##.......
#####.######

Popis výstupu programu

Výstupom programu budú dva riadky. Prvý riadok obsahuje reťazec "X sekund", kde X je počet sekúnd za ktorý sa Matfyzák môže dostať k východu. Druhý riadok riadok popisuje najrýchlejšiu cestu Matfyzáka k východu. Ak existuje niekoľko rovnako rýchlych najrýchlejších ciest, vypíšte ľubovoľnú z nich. Ak žiadna cesta k východu neexistuje, vypíšte namiesto výstupu hlášku "Matfyzak je navzdy strateny."

Povely Matfyzákovi sa zapisujú takto:

1 - Pohyb vľavo dole.
2 - Pohyb priamo dole.
3 - Pohyb vpravo dole.
4 - Pohyb vľavo.
6 - Pohyb vpravo.
7 - Pohyb vľavo hore.
8 - Pohyb priamo hore.
9 - Pohyb vpravo hore.
J(x y z) kde x, y, z sú z {1, 2, 3, 4, 6, 7, 8, 9} - Skok o najviac tri políčka v smere popísanom parametrami. Nie každý skok musí byť o tri políčka, ak chcete skákať menej, zapíšte menej parametrov.

(Prečo? Pozrite sa na numerickú klávesnicu.)

Jednotlivé príkazy oddeľujte medzerami.

Matfyzák samozrejme nedokáže vojsť do steny, a nikdy nesmie opustiť obrazovku. Ešte raz pripomínam, že pohyb trvá jednu sekundu, a skok trvá toľko sekúnd, o koľko políčok sa skáče. Čas strávený pádmi zanedbávame.

Jedna možná najkratšia cesta k východu pre vstup z príkladu je popísaná takto:

13 sekund
6 6 9 9 J(6 6 3) 6 6 6 J(9 7) 4

Matfyzák teda prešiel tieto políčka (toto váš program nemusí vykresľovať):

....+++.#V+.
...+#..+###+
M++##..++++.
#####.######

Po prvom skoku Matfyzák spadol o jedno políčko na plošinu pod ním. Celá cesta trvala 13 sekúnd.

Poznámky

Svoj program si môžete otestovať na niekoľkých vstupoch ktoré nájdete na platform.zip.

No a jeden tip na koniec: ak si s úlohou neviete rady, skúste sa najprv zamyslieť nad tým, ako by ste to riešili keby Matfyzák nevedel skákať.

FAQ

Q: Prejde Matfyzák medzerou medzi dvoma plošinami ktoré sa dotýkajú v rohu?

A: Áno, v tejto situácii je povolený krok 9 (vpravo hore):

.#.
.M#
###

Q: Je povolené skákať na políčko kde môže Matfyzák prejsť bez skákania?

A: Áno. Toto je tiež jedno korektné riešenie príkladu:

J(6) J(6) J(9) J(9) J(3 6 9) J(6) J(6) J(6) J(9 7) J(4)

Q: Môže sa stať že hneď na začiatku stojí Matfyzák vo východe?

A: Rozmyslite si ako by také zadanie vyzeralo...