Algoritmizace – 12. cvičení
Cesta králem na šachovnici (délka)
Řešte úlohu Cesta králem na šachovnici (délka) v ReCodExu. Program bude hledat nejkratší cestu šachovým králem na šachovnici , kde na některá políčka nelze vstoupit.
Můžete použít šablonu, která za vás vyřeší načítání vstupu (v původním vstupu jsou souřadnice políček 1 až 8, ale v reprezentaci v šabloně jsou 0 až 7). Do šablony stačí doplnit procházení možných tahů krále (metoda get_neigbors) a dokončit předpřipravený kód pro bfs.
Nejkratší cesta v ohodnoceném grafu
Problém nejkratší cesty lze zobecnit na grafy s nezáporným ohodnocením hran, kde je délka cesty měřena součtem ohodnocení hran.
Nalezne algoritmus BFS nejkratší cestu i v tomto případě? Pokud ano, vysvětlete proč, pokud ne, sestrojte protipříklad.
Bipartitní grafy
Graf je bipartitní, pokud lze jeho vrcholy obarvit dvěma barvami tak, že sousední vrcholy jsou obarveny různě. Navrhněte efektivní algoritmus, který zjistí, zdali je zadaný graf bipartitní.
Vaše řešení můžete vyzkoušet na úloze Bipartitní graf v ReCodExu.
Nápověda
Použijte BFS nebo DFS.
Kružítka a pravítka
Řešte lehkou verzi úlohy Kružítka a pravítka ze soutěže Kasiopea. Lehká verze jde vyřešit pomocí BFS nebo DFS.