About

Soutěžní úloha Bílá paní
„Neboj se, žádní duchové přece nejsou.“
„Já se přece nebojím. Jenom se mi zdálo, že jsem támhle něco zahlédl...“
„...“
„Pomóc, bílá paní, utíkej kdo můžeš!“
Bílá paní s bezhlavým rytířem společně sledovali bezhlavě prchající turisty.
„Anenudítesesamadolevpodhradí,“ptalserytíř, „kdyžvšechnynávštěvníky
vyděsítetak,ženestačíutíkat?“ „Alene,jednimitamnechalitelevizorajána
něm sleduji ty, jak se to jmenuje ... telenovely. Jenom teď musím ten televizor
zase najít a v mém věku už není procházení zdí tak jednoduché jako zamlada.“
Pomoztebílépanínajítcestuktelevizoru.Musítenajítcestunejkratší,protožejejíoblíbená
telenovelaprávězačíná.Podhradí,vekterémsetelevizornachází,mápodobubludištěorozměru
až 80
×80 políček. Kromě jedné bílé paní a jednoho televizoru se v bludišti nachází prázdná
políčka, zdi a zvědové. Zvědové jsou zvědavci, kteří se snaží objevit bílou paní. Kdyby se to
nějakémupovedlo,muselabyhobílápanívyhnatanestihlabykvůlitomusvůjoblíbenýpořad,
proto se bílá paní musí všem zvědům vyhnout.
Popis formátu bludiště
Bludiště je uloženo v textovém souboru, jehož řádky jsou oddělenydvojicíznakůCRaLF.Naprvnímřádkusenacházímezerou
oddělená dvě přirozená číslaS≤ 80 a Ř
≤ 80 – počet sloupců
a řádků bludiště. Na každém z následujících Ř řádků se nachází
popisS políček bludiště, která mohou být následující:
•.: volné políčko
•X: zeď
•&: bílá paní, v celém bludišti je přesně jedna
•#: televizor, v celém bludišti je přesně jeden
•@: zvěd. Každý zvěd má vlastní trasu, po které se pohybuje. Trasa je složena z nejvýš
osmi pohybů a po jejím provedení je zvěd vždy zpátky na políčku, ze kterého vyšel. Trasa
je v souboru uvedena ihned za zvědem a skládá se z pohybů:
◦<: vlevo ◦>: vpravo ◦^: nahoru ◦v: dolů
Příklad bludiště: soubor s bludištěm
5 5
&X...
.X.@^>v<.
.X.X.
@>><<..X.
..X#.
rozfázované pohyby zvědů
&X... &X.@. &X..@ &X...
.X.@. .X... .X... .X..@
.X.X. .X.X. .X.X. .X.X.
@..X. .@.X. ..@X. .@.X.
..X#. ..X#. ..X#. ..X#.
Pohyb v bludišti
Bílá paní se v bludišti v každém kroku pohne v jednom ze čtyř směrů – vlevo, vpravo, nahoru
či dolů. Pohyb je v každém kroku povinný, není možné zůstat stát. Cílem bílé paní je dostat
se v co nejmenším počtu kroků na políčko s televizorem. Bílá paní nesmí být o
ramovat hledání nejkratší cesty v bludišti, nebo editor bludiště, nebo
obojí. Pokud budete pracovat na obou úkolech, naprogramujte je do jediného programu.
1) Hledání nejkratší cesty v bludišti [70% bodů]
Váš program načte bludiště z uživatelem zvoleného souboru. Můžete přitom předpokládat, že
soubor obsahuje synatkticky korektní bludiště zapsané ve výše popsaném formátu.
Postupně přidávejte funkce v pořadí, v jakém jsou uvedeny:
• V bludišti, ve kterém nejsou zvědové, najděte libovolnou nejkratší cestu od bílé paní k televizoru.Bílápanínesmínikdyvstoupitnapolíčkosezdí.Zobraztetutocestuajejídélku,
případně vypište, že taková cesta neexistuje.
◦ Nejkratší cestu zobrazte interaktivně – zobrazujte postupně jednotlivé kroky bílé
paní a umožněte uživateli přejít o krok vpřed a o krok vzad.
• V bludišti, ve kterém nejsou zvědové, najděte libovolnou nejkratší cestu k televizoru, na
které musí bílá paní co nejméně krát projít zdí. Důležitější je projít co nejmenším počtem
zdí, takže libovolně dlouhá cesta bez průchodu zdí je lepší než jakkoliv krátká cesta, na
které musí bílá paní jednou projít zdí. Jako průchod zdí se počítá každý krok, který končí
na políčku se zdí. Nalezenou cestu včetně délky zobrazte, případně vypište, že taková
cesta neexistuje.
◦ Nejkratší cestu zobrazte interaktivně.
• V bludišti se zvědy najděte libovolnou nejkratší cestu od bílé paní k televizoru. Na cestě
nesmí bílou paní objevit žádný zvěd a bílá paní nemůže procházet zdí. Nalezenou cestu
včetně délky zobrazte, případně vypište, že taková cesta neexistuje.
◦ Nejkratší cestu zobrazte interaktivně, včetně pohybu zvědů.
• V bludišti se zvědy najděte libovolnou nejkratší cestu k televizoru, na které musí bílá
paní co nejméně krát projít zdí. Stejně jako v předchozím případě je důležitější projít
co nejmenším počtem zdí. Na cestě nesmí bílou paní samozřejmě objevit žádný zvěd.
Nalezenou cestu včetně délky zobrazte, případně vypište, že taková cesta neexistuje.
◦ Nejkratší cestu zobrazte interaktivně, včetně pohybu zvědů.
2) Editor bludiště [30% bodů]
Postupně přidávejte funkce v pořadí, v jakém jsou uvedeny:
• Úprava bludišť bez zvědů:
◦ Načtěte a zobrazte bludiště.
◦ Umožněte vytvořit nové prázdné bludiště zadaných rozměrů. Bílá paní je vlevo nahoře,
televizor vpravo dole.
◦ Dovolte editaci bludiště – přesun televizoru na vybrané políčko, přesun bílé paní na
vybrané políčko, vytváření a rušení zdí.
◦ Umožněte uložení bludiště.
• Úprava bludišť obsahujících zvědy. Kromě právě uvedených funkcí naprogramujte následující:
◦ Umožněte editaci zvědů – vytvoření nového zvěda, odstranění existujícího zvěda,
přesun zvěda (včetně jeho trasy) na vybrané políčko, úprava trasy zvěda. Při úpravě
trasy zkontrolujte, že se po jejím provedení vrátí zvěd na počáteční pozici.
◦ Dovolte uživateli zvolit režim, ve kterém se interaktivně zobrazují pohyby zvědů
v bludišti. Uživatel může přejít o krok vpřed a o krok zpět.