od Davpe » 20. 1. 2012 16:29
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.
(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.
[b]Zadání[/b]
Zadání podrobně [url=http://www.ksi.mff.cuni.cz/~jirasek/zaptest/2012_01_20_platform.php]zde[/url].
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
[b]Čas[/b]
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.
[b]Moje řešení[/b]
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.
[attachment=0]plosinovka.zip[/attachment]
(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.)
[b]Komentář[/b]
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.