HW04: Riešič bludísk | PB071 Nízkoúrovňové programování

Autoři zadání	Miroslav Patlevič Tomáš Waldsberger Dávid Šutor
Odevzdávané soubory	`.c` `.h`
Začátek odevzdávání	viz diskusní fórum
Další odevzdání navíc do	2024-04-24 24:00
Konec odevzdání	2024-05-01 24:00
Vzorová implementace	`/home/kontr/pb071/hw04/maze`

Kostra úkolu

Predstavenie úlohy

Tvoja stará mama veľmi rada navrhuje bludiská. Jedného dňa prišla za tebou s prosbou o pomoc. Vo svojom počítači ti ukázala zbierku ňou navrhnutých bludísk a požiadala ťa o to, aby si našiel v každom bludisku najkratšiu cestu z jedného konca do druhého. Keďže nemáš veľa času, rozhodol si sa vytvoriť program, ktorý túto najkratšiu cestu v bludisku nájde.

Zadanie

Vašou úlohou je napísať program, ktorý načíta z textového súboru obrázok bludiska, overí, že sa v ňom nachádza validné bludisko, nájde v ňom najkratšiu cestu zo začiatku bludiska do jeho konca a vyriešené bludisko vypíše do zadaného súboru.

Overenie validity bludiska je dôležitou súčasťou zadania, preto sa program bude spúšťať jedným z nasledujúcich spôsobov:

./maze check INPUT_FILE
./maze solve INPUT_FILE OUTPUT_FILE

check kontroluje validitu vstupného súboru, zatiaľ čo solve vyrieši bludisko a zapíše výsledok do výstupného súboru.

Formát bludiska

Bludisko bude zadané v textovom súbore, v ktorom sa budú nachádzať nasledujúce znaky:

#

Tento znak predstavuje stenu bludiska.

X

Tento znak predstavuje vstup/východ z bludiska.
Vo validnom bludisku by sa mali nachádzať práve dva takéto znaky

(medzera)

Predstavuje voľné miesto, cez ktoré môže viesť cesta k východu

Žiadne ďalšie znaky sa vo vstupnom súbore nachádzať nesmú!

Za bludisko považujeme akúkoľvek oblasť, ktorá:

je zvonku súvislo uzavretá znakmi #
- Znamená to, že táto oblasť je ohraničená postupnosťou znakov # a práve dvoch znakov X tak, že každý znak v postupnosti je z iného políčka v bludisku a zároveň každé dva susediace znaky v postupnosti sa v bludisku nachádzajú bezprostredne buď vertikálne alebo horizontálne vedľa seba.
- Ľudovo povedané, stena ohraničujúca bludisko musí byť taká, aby po nej hadík zo známej hry na tlačidlové mobilné telefóny vedel prejsť a nakoniec sa sám uhryznúť do chvosta.
práve na dvoch miestach sa nachádzajú znaky X
znaky X sa nachádzajú v najvonkajšej stene bludiska tak, že v okolí znaku X sa nachádzajú práve dva znaky #, a to horizonatálne alebo vertikálne oproti sebe.
- Toto pravidlo zabraňuje vzniku nepriechodných vstupov.

V prípade, že existuje niekoľko podbludísk, tak za bludisko sa považuje čo najväčšia ohraničená oblasť s čo najdlhšou najvonkajšou stenou.

Mimo bludiska sa nesmú nachádzať žiadne samostatne stojace znaky X alebo #. Na medzery sa táto požiadavka nevzťahuje.

Vo vstupnom súbore sa musí nachádzať len jedno bludisko.

Formát výstupu

Program do výstupného súboru vypíše načítané bludisko doplnené o nájdenú najkratšiu cestu. Nájdená najkratšia cesta bude vyznačená znakom o, bude viesť medzi dvoma znakmi X a vedie vnútrom bludiska. Znaky X nahradí program vo výstupe taktiež znakmi o.

Program vypisuje vyriešené bludisko bez prázdnych riadkov. Prípadné biele znaky na konci riadkov nevypisuje (každá neprázdna sekvencia medzier musí byť nasledovaná znakom # alebo o). Naľavo od bludiska sa navyše nesmú nachádzať súvislé stĺpce medzier.

Príklad

Vstupný súbor:

 ###
 X X
 ###

Výstup:

###
ooo
###

Požiadavky

`check`

Za prepínačom check nasleduje cesta k vstupnému súboru obsahujúcemu bludisko.
Program načíta vstupný súbor a skontroluje validitu bludiska popísanú v sekcii Formát bludiska.
Ak vstupný súbor zadaným požiadavkám nevyhovuje, program vypíše na štandardný chybový výstup zrozumiteľnú chybovú hlášku a skončí s nenulovým návratovým kódom.
V prípade, že bludisko je validné, program skončí s nulovým návratovým kódom.

`solve`

Za príkazom solve nasleduje cesta k vstupnému súboru obsahujúcemu bludisko a za ňou cesta k výstupnému súboru, do ktorého program vypíše bludisko s vyznačenou najkratšou cestou.
Ak vstupný súbor nie je validný, program vypíše na štandardný chybový výstup zrozumiteľnú chybovú hlášku a skončí s nenulovým návratovým kódom, pričom výstupný súbor nevznikne.
Po overení validity bludiska ho program vyrieši a vypíše riešenie do súbora podľa požiadaviek v kapitole Formát výstupu.
V prípade, že bludisko nemá riešenie, program informuje používateľa zrozumiteľnou hláškou na chybovom výstupe a skončí s návratovou hodnotou 0. Výstupný súbor nevznikne.
Ak nedošlo k chybe, program skončí s návratovou hodnotou 0, inak končí s nenulovou návratovou hodnotou a zrozumiteľnou chybovou hláškou na chybovom výstupe.

Hľadanie steny bludiska nie je zložité. Stačí si predstaviť, že vonkajšia stena je plot od záhrady. Obchádzate ho dovtedy, kým nenájdete jeho vchod a potom plot nasledujete dovtedy, kým ho celý neobídete.

V prípade, že došlo k akejkoľvek chybe pri práci so súbormi alebo pamäťou, tak program vypíše na štandardný chybový výstup zrozumiteľnú chybovú hlášku a skončí s nenulovým návratovým kódom. Rovnako sa bude správať, ak bude spustený s iným, než očakávaným počtom parametrov.

Chybovú hlášku tvorí jeden riadok zakončený znakom \n.

Bonusové rozšírenia

Vykreslenie bludiska do obrázka [10 bodov]

Doimplementujte príkaz draw, ktorý vykreslí zadané bludisko do bitmapového súboru. Program sa bude spúšťať nasledovne:

./maze draw [-c|--color "#RrGgBb"] [-s|--scale INTEGER] INPUT_FILE OUTPUT_FILE

-c "#RrGgBb" alebo --color "#RrGgBb"
- Nepovinný parameter.
- Špecifikuje farbu, ktorá bude použitá na vykreslenie najkratšej cesty v bludisku.
- Farba je zadaná ako šestica šestnástkových čísiel. Rr je hodnota červenej zložky, Gg zelenej a Bb modrej.
- V prípade, že tento parameter nie je zadaný, použije sa červená farba (#FF0000).
-s INTEGER alebo --scale INTEGER
- Nepovinný parameter
- Špecifikuje koeficient, ktorým sa násobia rozmery obrázka.
- V prípade, že tento parameter nie je zadaný, použije sa hodnota 1.
- Koeficient 3 spôsobí, že veľkosť jedného políčka nebude 1x1 px ale 3x3 px

Nie je potrebné kontrolovať vstupný súbor na validitu bludiska (môžeme chcieť vykresliť aj nevalidné prípady) ale je nutné skontrolovať, či obsahuje iba povolené znaky.

Stena bludiska je vyplnená čiernou farbou (#000000), voľné miesta (a prípadné vstupy do bludiska) sú vyplnené bielou farbou (#FFFFFF). Veľkosť jedného políčka v bludisku je určená pomocou prepínača -s|--scale. Pokiaľ nie je táto hodnota uvedená, použije sa hodnota 1x1 px. Šírka výsledného obrázka bude odpovedať dĺžke najdlhšieho riadka v súbore krát hodnota prepínača -s|--scale. Výška výsledného obrázka bude odpovedať počtu riadkov v súbore krát hodnota prepínača -s|--scale.

Pri vykresľovaní bludiska do obrázka odporúčame použiť knižnicu, ktorú nájdete v súboroch libbmp.c a libbmp.h. Ak sa rozhodnete nepoužiť priloženú knižnicu a napíšete si vlastnú, uistite sa, že sa vaše obrázky binárne zhodujú so vzorovou implementáciou na Aise (rovnaká hlavička súboru, kompresia…).

Poznámky

Na nájdenie najkratšej cesty v bludisku je dobré si bludisko predstaviť ako neorientovaný graf. Na nájdenie najkratšej cesty v grafe je ideálne použiť algoritmus BFS. Je to jeden zo základných grafových algoritmov, ktorý využíva dátovú štruktúru FIFO (queue). Najkratšiu cestu v grafe je možné nájsť pomocou algoritmu BFS s využitím predchodcov uzlov v grafe.

V kostre úlohy je implementácia radu (česky fronta) už dodaná.

// Pseudokód BFS
procedure BFS(graph, root)
{
    let Q be queue;
    label root as explored;
    set predecessor of root to nil;
    Q.enqueue(root);
    while Q is not empty {
        vertex := Q.dequeue();
        if vertex is the goal {
            break;
        }
        for next_vertex in graph.adjacent_edges(vertex) {
            if next_vertex is not labeled as explored {
                label next_vertex as explored;
                set predecessor of next_vertex to vertex;
                Q.enqueue(next_vertex);
            }
        }
    }
}

Viac informácií k dispozícii napríklad na anglickej wikipédii.

Reprezentáciu grafu je nutné si poriadne rozmyslieť. Keďže bludisko je v podstate matica, určite neodporúčame si alokovať pre každé políčko vlastný uzol.

Odporúčame rozdeľovať riešenie do viacerých súborov. Dekompozícia je na vás. Odovzdať môžete ľubovoľné .c a .h súbory, avšak CUT testy v kostre očakávajú, že funkcia main() bude v main.c.

Na jednoduchú tvorbu bludísk môžete využiť online editor bludísk.

Na účely testovania programu garantujeme, že ak existuje v bludisku viacero ciest, práve jedna z nich je najkratšia.