TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Zadání
Úkolem je realizovat program, který dokáže vypočítat efektivní průchod labyrintem s diamanty.
Vstupem programu je mapa labyrintu. Mapa je předaná v textové podobě na standardním vstupu. Pro jednoduchost předpokládáme, že mapa má obdélníkový tvar. V mapě jsou naznačené diamanty (znaky *), nepřekonatelné zdi (znak #) a volné prostranství (znak mezera). Labyrint má jediný vchod v některé z obvodových zdí. Zadávání labyrintu probíhá po řádcích. Každý řádek vstupu představuje jeden řádek mapy. Zadávání celého labyrintu je signalizováno koncem souboru (feof(stdin) je aktivní).
Výstupem programu je informace o tom, kolik diamantů lze z labyrintu odnést a dále informace o tom, kolik kroků v labyrintu je na to nejméně potřeba. Předpokládáme, že se můžeme pohybovat pouze ve směru vlevo/vpravo/nahoru/dolů, kde každý pohyb (o jedno políčko) je právě jeden krok. Cesta vždy začíná a končí vstupem do labyrintu.
Program musí být schopen detekovat nesprávný vstup. Pokud je zadaná neplatná mapa, program vypíše chybové hlášení a ukončí se. Formát chybového hlášení je zřejmý z ukázek níže. Za chybu je považováno:
*
v zadání labyrintu byly jiné znaky než mezera, hvězdička, křížek a odřádkování,
*
labyrint není obdélníkového tvaru,
*
labyrint není obehnán zdí,
*
do labyrintu není žádný vstup nebo naopak více než jeden vstup,
*
v labyrintu je celkem více než 20 diamantů (pro jednoduchost předpokládáme toto omezení).
Program je testován v omezeném prostředí. Je omezena doba běhu i dostupná paměť. Doba běhu je nastavena tak, aby vyhovělo i řešení hrubou silou bez heuristik. Výjimkou je bonusový test, který řešení bez alespoň základní heuristiky (zahazování neperspektivních průchodů) nezvládne časově.
Nápověda
*
Nejprve si spočtěte matici vzdáleností mezi jednotlivými diamanty a mezi vstupem a diamanty. Zde se hodí algoritmus procházení do šířky (BFS) ve variantě semínkového vyplňování (seed fill).
*
Sestavte cestu, která začíná a končí vstupním bodem a prochází všemi diamanty. Takových cest existuje mnoho (počet_diamantů faktoriál), postupně vypočtěte jejich délky (vzdálenosti znáte z matice vzdáleností vypočtené v předchozím bodě) a určete nejkratší z nich.
*
Pro vygenerování všech možných cest budete potřebovat rekurzi.
*
Může se stát, že některé diamanty nebudou dostupné, takové musíte z výpočtu cest vyloučit.
*
Popsané řešení (hrubou silou) není příliš rychlé. Proto je volen malý rozsah úlohy (do 20 diamantů), aby výpočet skončil v rozumné době. Řešená úloha (nalezení nejkratší cesty mezi diamanty) je optimalizační variantou problému obchodního cestujícího (TSP - traveling salesman problem). Úloha TSP patří mezi tzv. NP-úplné problémy, tedy problémy, pro které neznáme efektivní algoritmus jejich řešení. Úlohy tohoto typu dokážeme řešit pouze zkoušením všech možností, což mívá vysokou operační složitost (zde například faktoriální). Řešení bývá možné urychlit heuristikami, kdy se preferují perspektivní řešení (zde např. krátké cesty), naopak neperspektivní možnosti řešení (zde např. velmi dlouhé cesty) se buď vůbec nepočítají nebo se odkládají na později.
*
Referenční řešení používá dvě jednoduché heuristiky - pokud v průběhu vytváření cesty mezi diamanty zjistí, že cesta je delší než dosavadní nalezené minimum, dále již cestu nedokončuje a začne vytvářet cestu jinou. Druhou možností je preference cesty směrem k nejbližšímu diamantu (při vytváření cesty se první zkusí nejbližší diamant). Tím se program relativně brzy dostane k rozumné délce cesty (ale pozor - takto nalezená cesta nemusí být nejkratší). Výhodné je obě popsané heuristiky spojit.
Ukázka práce programu:
Zadejte mapu:
# ######
# * *#
# * #
########
Diamantu: 3
Delka cesty: 14
Zadejte mapu:
##############
#
############ #
#* #
##############
Diamantu: 1
Delka cesty: 50
Zadejte mapu:
##################### ######
#* # #
############ # #############
# # # #
# ############ # ######### #
# *# # #
# ############## # #########
# # #
# ######################## #
#* * * #
############################
Diamantu: 5
Delka cesty: 148
Zadejte mapu:
#############
#*# * # * #*#
# # # # # # #
# * # * # * #
###### ######
Diamantu: 7
Delka cesty: 46
Zadejte mapu:
############################
# * * #
# ######## #
# * # * # #
# # ###### #
# * * #
# ############ * #
# # * * # #
# # * * # #
# * ############ * #
# * #
###################### #####
Diamantu: 10
Delka cesty: 86
Zadejte mapu:
#############
# * # #
# # #
# # *#
###### ######
Diamantu: 1
Delka cesty: 12
Zadejte mapu:
##### #######
# #
# #
# *#
###### ######
Nespravny vstup.
Zadejte mapu:
#############
# #
# a #
# *#
###### ######
Nespravny vstup.
Nahlásit jako SPAM
IP: 174.36.199.–
Zjistit počet nových příspěvků
