Zahradník se stará o zahradní bludiště. Do bludiště přichází mnoho návštěvníků a zahradník nechce chod v bludišti omezovat na dlouhou dobu. Proto potřebuje vyhledat cesty, kterými při průchodu bludištěm musí projít každý návštěvník a pro úpravu kterých tudíž musí být bludiště uzavřené. Pomozte zahradníkovi tyto cesty v bludišti vyhledat.

Na vstupu je dáno obdélníkové bludiště – viz předloha níže. Šířka bludiště je dána počtem znaků na prvním řádku. Délka bludiště je dána počtem načtených řádků. Keře v bludišti, kterými jsou ohraničené cesty, jsou v bludišti označeny znakem #, průchozí místa znakem . (tečka). Do bludiště se vchází vlevo nahoře a vychází se vpravo dole.

Výstupem programu je bludiště, v němž jsou místa, kudy je nevyhnutné projít (dále označeno jako „hledaná místa“) vyznačena znakem ! (vykřičník).

Bludiště na vstupu kompletně načtěte. Zkontrolujte, zda je bludiště korektně zadané. Kontrola vstupu a případné vypsání chyby musí být provedeno v následujícím pořadí:

• Error: Bludiste neni obdelnikove! – některý z řádků má jinou délku než první řádek
• Error: Vstup neni vlevo nahore! – druhý znak v prvním řádku není .
• Error: Vystup neni vpravo dole! – předposlední znak v posledním korektně načteném řádku není .
• Error: Sirka bludiste je mimo rozsah! – šířka bludiště (počet znaků na řádku) musí být v rozmezí 5 až 70 znaků
• Error: Delka bludiste je mimo rozsah! – délka bludiště musí být v rozmezí 5 až 50 řádků
• Error: Bludiste obsahuje nezname znaky! – znak na vstupu není # nebo .
• Error: Bludiste neni oplocene! – neplatí, že kromě vstupu a výstupu z bludiště jsou všechny znaky po obvodu bludiště #

Cesty procházení bludištěm lze získat metodou prohledávání do hloubky s možností opravy, pokud vejdeme do „slepé“ uličky (backtracking). Tímto algoritmem dokážeme poměrně jednoduše najít jednu cestu bludištěm. Úloha požaduje prohledání stavového prostoru problému a vyhledání všech možných cest v bludišti tak, abychom dokázali vyhledat místa, kudy všechny cesty bludištěm prochází. Právě tato místa potřebuje zahradník znát, aby věděl, kdy má bludiště uzavřít.

Vzhledem k exponenciální časové složitosti tohoto postupu řešení problému je vhodné se zamyslet nad optimalizací řešení. Při hledání optimálního řešení mohou napomoci následující úvahy:

• Všechna hledaná místa se nachází na první nalezené cestě bludištěm
• Hledanými místy jsou vstup do bludiště a výstup z bludiště
• Části první nalezené cesty, které tvoří cyklus s některou z dalších možných cest bludištěm nejsou hledanými místy – dají se obejít po druhé části cyklu
• Když hledané místo zahradíme (například znakem #), cesta bludištěm nebude existovat. Naopak, když zahradíme místa, která nejsou takto exponovaná, cestu bludištěm najdeme snadno.
• Vhodným zahrazením cest v bludišti fiktivními „keři“ lze značně omezit počet možných cest a značně urychlit nalezení řešení
• Při procházení bludištěm se v každém kroku lze (s ohledem na rozmístění keřů) rozhodnout, zda další cesta půjde vlevo nebo vpravo, nahoru nebo dolů. Zvažte, zda vhodná posloupnost prohledání těchto možností (například vlevo, nahoru, vpravo, dolů nebo dolů, nahoru, vlevo, vpravo) nedokáže ovlivnit efektivnost řešení. Uvažujeme cesty bludištěm z levého horního do pravého dolního rohu. Posloužit může i myšlenka topologického uspořádání vrcholů v grafu.

Rychlost je srovnávána v opakovaných testech s rychlostí (časem) výpočtu referenčního řešení. Bodově jsou hodnocena řešení, která potřebují čas menší než je trojnásobek času referenčního řešení.

Veřejné testovací soubory - DSA_HW01.

clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17

javac *.java
java -classpath Maze

prohledávání stavového prostoru do hloubky
backtracking
složitost úlohy a její optimalizace