# Zápočtový test 20.01.2012 - Matfyzák v platformovke

<{ForumPost(poster="Davpe", timestamp=2012-01-20 16:29:04)}>
**Zadání**  
Zadání podrobně [zde](http://www.ksi.mff.cuni.cz/~jirasek/zaptest/2012_01_20_platform.php).   
Ve stručnosti: Máme 2D mapu, se pevnými objekty (tvoří platformy), volnými poli, matfyzákem a východem. Pohyb matfyzáka je buď jeden krok (v tomto případě se hýbe do 8 směrů jako kdyby byl na numlocku číslo 5) s tím, že se musí přesunout na nějakou plošinu. Anebo dvojskoky či trojskoky (přesune se o dvě/tři pole, jako kdyby udělal dva/tři kroky za sebou, ale může být i ve vzduchu). Funguje gravitace (pokud udělá krok do prázdna a zrovna neskáče, padá dolů). Nesmí vylézt z mapy (ani třeba při skoku). Výstup je posloupnost kroků (a pokud je to skok, tak jej rozlišit), které dovedou matfyzáka k východu. Tato posloupnost musí být nejkratší možná.  
  
Příklad vstupu (Vždy korektní, čísla omezená max 50).  
4 12  
........#V..  
....#...###.  
M..##.......  
#####.######  
  
Příklad výstupu  
13 sekund  
6 6 9 9 J(6 6 3) 6 6 6 J(9 7) 4  
  
**Čas**  
Začátek: 10:30  
Čas: 3 a půl hodiny  
  
Po třech hodinách odešel první, čas byl prodloužen do 15:00, odešel jsem 20 minut před ním. Přede mnou odešli (úspěšně) asi 3 lidi.  
  
Povolena byla MSDN library a cplusplus.com a Jiraskovy stranky. Internet vypnuty nebyl. Jirasek nas pravidelne (skoro porad) obchazel a koukal nam pres rameno.  
  
**Moje řešení**  
Váhal mezi Dijkstrou a BFS, nakonec jsem zvolil to druhé. Netuším, co by byla lepší volba. Žádnou optimalizaci jsem nedělal. Pokud by nekoho zajimaly moje zdrojaky, zde jsou.

plosinovka.zip

(BTW: Az ted jsem zjistil, ze Jirasek nema uplne konzistentni vstupy. V prvnim vstupu nema na konci souboru prazdny radek, v ostatnich uz ano. Docela mi to pak delalo problem, protoze se mi chybne nacetla mapa. Ve zdrojacich vyse uz jsem to opravil.)  
  
**Komentář**  
Bylo to spíše pracné a blbě debugovatelné. Jako céčkařovi mi z C++ stačila znalost vectoru, queue, pair a pak I/O. Povedlo se mi nachytat se na souřadnice. Klasicky je 0 dole a nahoru to roste, pokud to máte jako řádky v poli, tak je to naopak, takže mi matfyzák padal nahoru apod. Pak už jen podivné chyby (díkybohu žádná nebyla v algoritmu nebo tom důležitém jádru, jinak bych tam byl doteď), které jsem nějak zaplátoval.

*Attachments:*

- *[plosinovka.zip](/Forum%20archiv/Attachments/5144_b31b94c6ee35772d1d1fecb6831bb3a2)*

<{/ForumPost}>

<{ForumPost(poster="Premun", timestamp=2012-01-26 23:42:50)}>
Protoze ta mapa byla omezena na max 50x50, tak jsem pouzil uplne zakladni DFS "nad jednou mapou" a pro kazdy pole si pamatoval, jak jsem se tam zatim dostal nejrychleji.  
Bezelo to pod sekundu a za hodku a 3/4 jsem mel nejkratsi cestu. Pak mi teda dalsi hodinu trvalo ji vypsat, ale to uz je spis moje blbost..
<{/ForumPost}>