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

Základní kurs objektově orientovaného programování v C++. Třídy a objekty, zapouzdření, metody, plymorfismus. Abstraktní datové typy, přetěžování. Kontejnery, iterátory, algoritmy. Šablony, generické programování, kompilační polymorfismus. Výjimky. Bezpečné a přenositelné programování, vazby na OS.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

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

Příspěvek od Davpe »

Zadání
Zadání podrobně zde.
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
(379.79 KiB) Staženo 304 x
(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.
Premun
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 6. 6. 2011 22:52
Typ studia: Informatika Mgr.

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

Příspěvek od Premun »

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..
Odpovědět

Zpět na „NPRG041 Programování v C++“