======== HW01 Prohledávání do hloubky ========
{{:courses:b6b36dsa:ukoly:bludiste.jpg?300 | Trojský zámek, Praha }}
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).
====== Kontrola vstupu ======
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ž 100 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ě ''#''
* ''Error: Cesta neexistuje!'' - neexistuje ani jedna cesta bludištěm
Detekovanou chybu na chybovém výstupu vypište a program ukončete. Vypsané chybové hlášení je ukončeno koncem řádku (znakem ''\n'').
====== Algoritmus řešení úlohy ======
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í již 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.
Časově nejefektivnější řešení budou bodově ohodnocena.
====== Kontrolní testy ======
Testovací soubory najdete {{ :courses:b6b36dsa:ukoly:dsa_hw01.zip |zde}}.
===== Základní formát výstupu =====
==== Příklad 1 – blud_1_01 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
#.#####
#.....#
#####.# | #!#####
#!#####
#!#####
#!!!!!#
#####!# | žádný | 0 |
==== Příklad 2 – blud_1_02 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| ##.###
#.####
..#####
#..$$$.#
#.##.## | žádný | Error: Bludiste neni obdelnikove! | 1 |
==== Příklad 3 – blud_1_03 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| ##.###
#.####
#.####
#..$$$
#.##.#
| žádný | Error: Vstup neni vlevo nahore! | 1 |
==== Příklad 4 – blud_1_04 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
..#####
#..$$.#
#.##### | žádný | Error: Vystup neni vpravo dole! | 1 |
==== Příklad 5 – blud_1_05 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.##
#.##
..##
#..$
#..# | žádný | Error: Sirka bludiste je mimo rozsah! | 1 |
==== Příklad 6 – blud_1_06 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
..#####
#..$$.# | žádný | Error: Delka bludiste je mimo rozsah! | 1 |
==== Příklad 7 – blud_1_07 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
..#####
#..$$.#
#.###.# | žádný | Error: Bludiste obsahuje nezname znaky! | 1 |
==== Příklad 8 – blud_1_08 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
..#####
#.....#
#.###.# | žádný | Error: Bludiste neni oplocene! | 1 |
==== Příklad 9 – blud_1_09 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
#.#####
#....##
#####.# | žádný | Error: Cesta neexistuje! | 1 |
==== Příklad 10 – blud_1_10 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
#.#####
#....#
#####.# | žádný | Error: Bludiste neni obdelnikove! | 1 |
===== Správnost výpočtu =====
==== Příklad 9 – blud_2_01 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.....#
#.....#
#.....#
#####.# | #!#####
#!....#
#.....#
#....!#
#####!# | žádný | 0 |
==== Příklad 10 – blud_2_02 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#.#####
#...###
#.....#
#####.# | #!#####
#!#####
#!..###
#..!!!#
#####!# | žádný | 0 |
==== Příklad 11 – blud_2_03 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.#####
#....##
#.##.##
#.....#
#####.# | #!#####
#!...##
#.##.##
#...!!#
#####!# | žádný | 0 |
==== Příklad 12 – blud_2_04 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.###############
#...#...........#
#.###.#####.#.#.#
#...........#...#
###############.# | #!###############
#!..#......!!!..#
#!###.#####.#.#.#
#!!!!!......#..!#
###############!# | žádný | 0 |
==== Příklad 13 – blud_2_05 ====
^ Vstup (stdin) ^ Výstup (stdout) ^ Chybový výstup (strerr) ^ Návratová hodnota ^
| #.##########
#..........#
#.#.######.#
#.#......#.#
#.#.####.#.#
#.#....#.#.#
#.#.#..#.#.#
#.#.#.##.#.#
#.#......#.#
#.######.#.#
#..........#
##########.# | #!##########
#!.........#
#.#.######.#
#.#......#.#
#.#.####.#.#
#.#....#.#.#
#.#.#..#.#.#
#.#.#.##.#.#
#.#......#.#
#.######.#.#
#.........!#
##########!# | žádný | 0 |
Tyto testovací soubory najdete v přiloženém akchivu.
Další testy na správnost výpočtu jsou utajené.
==== Příklad 14 – Velké bludiště ====
Na následujícím příkladu lze testovat rychlost výpočtu na velkých bludištích. Bludiště není součástí testovací sady, ale podobá se časové náročným testům.
#.#############################
#..........................#..#
#.#####################.......#
#.............................#
##############.################
#................##..#...#...##
#############...###.##.#...#.##
#...................#..###.#.##
#################.####...#.####
#........................#....#
#.##########################..#
#.............................#
###########.#################.#
#.#.......#.#...#.#...#...#...#
#.#.#####.####..#.#.#.#.#.#.###
#.#.....#.......#.#.#.#.#.....#
#.###.#####.###.#.#.#.#.#.###.#
#.....#...#.#...#...#...#.#...#
#.....#.#...#.#########.#######
#.###.#.#.#.###.........#...#.#
#.....###.#...#.#########.#...#
#####...#####...#.........#...#
#.....###########....########.#
####.....##########.#######...#
########..........#.#.#.....#.#
#...####...########...#.#####.#
#.#.####.#####........#....##.#
#.#......####...###...###.###.#
#...######..#####...#####.###.#
###...............#######...#.#
#############################.#
===== Rychlost výpočtu =====
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í.
====== Odevzdání a hodnocení ======
Úlohu je možné řešit v programovacím jazyce ''Java'', ''Python'' nebo ''C/C++''.
Veřejné testovací soubory - {{:courses:b6b36dsa:ukoly:DSA_HW01.zip?400|DSA_HW01}}.
^ Název úlohy v BRUTE | **HW01** ||
^ Odevzdávané soubory | ''maze.py'' – zdrojový soubor v python3 ||
| ::: | ''Maze.java'' – zdrojový soubor v Java, název třídy Maze ||
| ::: | ''maze.c'', resp. ''maze.cpp'' – zdrojový soubor v C/Cpp ||
^ Argumenty programu | žádné ||
^ Kompilace pro jazyk C | clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17 ||
^ Kompilace a spuštění \\ pro jazyk Java | javac *.java
java -classpath Maze ||
^ Očekávaná složitost | lepší než $\mathcal{O}(n^4)$ ||
| ::: | Koeficient pro čas výpočtu $3.0$ ||
^ Procvičované oblasti | prohledávání stavového prostoru do hloubky
backtracking
složitost úlohy a její optimalizace ||
^ Bodové hodnocení (celkem 10 bodů) | 2 body | blud_1_01 – blud_1_10 + 5 skrytých testů |
| ::: | 3 body | blud_2_01 – blud_2_05 + 3 skryté testy |
| ::: | 5 bodů | blud_3_01 – blud_3_20 – řešení časově stejné nebo lepší než referenční řešení |
^ Maximální počet uploadů | ''20'' Více uploadů je možných s odpovídající bodovou ztrátou ||