Tomáš má veľa práce. Napríklad musí urobiť úlohu do Prasku. Preto sa teraz Tomáš hrá Minecraft s Riškom a Maxom. Tomáš je však hrozne nešikovný, a tak sa mu podarilo zobudiť draka, ktorý zapálil les, v ktorom sa Tomáš skrýval. Tomáš nechce zase zhorieť, takže by rád vedel, kedy sa ktorý strom zapáli. Poprosil preto Riška a Maxa o pomoc. Riško však stavia lokomotívu a Maxo dokončuje kláštor. Pomôžte a zachráňte chudáka Tomáša vy, aby mohol konečne urobiť tú úlohu do Prasku.
Les si predstavíme ako štvorcovú mriežku. Na každom políčku sa buď nachádza strom, alebo je políčko prázdne. Na začiatku horí niekoľko stromov.
Každú minútu sa oheň rozšíri zo všetkých horiacich stromov na ich susedov. Za susedné považujeme stromy, ktoré sa nachádzajú vedľa seba vodorovne alebo zvislo – nie diagonálne. Raz zapálený strom horí až do konca. Cez prázdne miesta sa oheň nešíri.
Pozrite sa na obrázok lesa, v ktorom na začiatku horí jeden strom.

Vyznačte stromy, ktoré začnú horieť po prvej, druhej, … minúte. Stromy, ktoré začnú horieť v rovnakej minúte, vyznačte rovnakou farbou. Ako dlho bude trvať, kým všetky stromy začnú horieť?
Vráťme sa k prípadu, keď na začiatku horí iba jeden strom A. Tomáš tvrdí, že ak existuje cesta zo stromu A do stromu B pozostávajúca zo štyroch krokov medzi susednými stromami, tak strom B začne horieť najneskôr po štyroch minútach. Má Tomáš pravdu? Čo ak existuje aj kratšia cesta?
Teraz na začiatku horia dva stromy.

Opäť vyznačte stromy, ktoré začnú horieť po prvej, druhej a tretej minúte. Čo sa zmenilo oproti predchádzajúcemu prípadu? Ktoré stromy sa teraz zapália skôr ako v prípade, keď horel iba prvý strom A?
Vráťme sa k prípadu, keď na začiatku horí iba strom A. Tomáš našiel cestu zo stromu A do stromu B, ktorá pozostáva zo štyroch krokov medzi susednými stromami. Usúdil, že strom B začne horieť presne po štyroch minútach. Má Tomáš vždy pravdu?
Tomáš dostal nápad: spustí BFS1 osobitne z každého horiaceho stromu a pre každý strom si zapamätá najkratší čas, ktorý mu vyšiel. Vedel by však celý les preskúmať aj jediným spustením BFS? Ako by musel upraviť jeho začiatok?
Čo sa stane so stromami, ku ktorým sa oheň nikdy nedostane? Ako ich vieme rozpoznať?
Pred začiatkom šírenia požiaru Tomáš zapálil ešte jeden strom, ktorý dovtedy nehorel. Môže sa stať, že sa teraz niektorý strom zapáli neskôr ako v pôvodnom prípade? Svoje tvrdenie vysvetlite.
BFS je algoritmus na prehľadávanie grafu do šírky. Viac si o ňom môžeš prečítať na KSP kuchárke ↩
Súťaž PRASK zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre stredoškolákov
Tímová matematicko-fyzikálna súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania