Pomoc s Ukolem v C za penezni odmenu!!!! – C / C++ – Fórum – Programujte.com

prosim o pomoc s ukolem, zde je zadani:

Úkolem je realizovat program, který dokáže najít cestu ve 2D bludišti.

Vstupem programu je zadání bludiště. Bludiště je zadáno jako 2D čtverečková mapa na standardním vstupu. Každý řádek vstupu představuje jeden řádek mapy. Délka řádky ani počet řádek nejsou omezené. Na řádce se mohou vyskytovat následující znaky:

* hvězdička, která reprezentuje zeď,
* mezera, která reprezentuje volný prostor,
* znak velké S, který označuje startovní pozici,
* znak velké E, který označuje cilovou pozici.

Výstupem programu je oznámení o vzdálenosti ze startovního bodu do cílového bodu. Předpokládáme, že pohybovat se lze pouze ve 4 základních směrech (nahoru, dolů, vpravo a vlevo) po volných políčkách. Vypočtená vzdálenost startu a cíle je celkový počet takových tahů (tzv. Manhattanská vzdálenost). Program je dále schopen detekovat, že cíle nelze dosáhnout (neexistuje k němu cesta). Formát výpisu je zřejmý z ukázek níže.

Program detekuje chybu, oznámí ji a ukončí se, pokud je na vstupu špatně zadané bludiště. Za chybu zadání je považováno:

* chybějící startovní nebo cílová pozice,
* více než jedna startovní nebo cílová pozice,
* jiný než obdélníkový tvar zadaného bludiště (nestejná délka řádek),
* skutečnost, že bludiště není ohraničeno souvislou "obvodovou" zdí,
* skutečnost, že v zadání bludiště jsou jiné znaky než mezera, hvězdička, S a E.

Počítejte s tím, že program běží v omezeném testovacím prostředí. Je omezena velikost dostupné paměti a doba běhu programu (5s na testovacím počítači, referenční program potřebuje pro výpočet cca 200ms). Při realizaci je zakázáno používat C++ datový typ string a datové kontajnery z STL (vector, list, ...). Jejich použití povede k chybě při překladu.


pokud mate zajem o pomoc, tak se ozvete, detaili zadani poslu.
ozvete se na mail nebo na icq 237010804
diky!!!

To resident_evil :
http://en.wikipedia.org/wiki/Breadth-first_search

To resident_evil : Zkus spíš rozepsat v čem je problém, přece aspoň něco musíš vědět :-)

To midin : Ti, co mají peníze, se nemusí svěřovat se svými problémy :smile3:

to smrdí ProgTestem

Progtest to je na 100% :)

"Délka řádky ani počet řádek nejsou omezené." Hnus velebnosti. Uz samotne vytvoreni mapy bude pakarna a prochazani je na maslu. Vlnka to nestihne. Pokud je to nejake slusne bludiste, ktere ma spoustu zdi, tak by stalo za to si udrzovat spojak policek "hranice pseudovlny" a ty posunovat pripadne na rozcesti vytvorit dalsi. Samozrejme si udrzovat v bunkach boolean" tady uz sem byl a podle toho neposunout hranici.Cesta neni pokud nejde uz posunout hranici. vlastne ted uz to nezni tak slozite :-)

Mne to prijde ako klasická grafárina. Keď som to raz robil v Pascale tak som použil Djiskrov algoritmus a išlo to.

To Krychlik : To jsou nesmysly, na tohle stačí BFS. Vytvaření mapy bude v pohodě, načtení pomocí getline, kontrola jestli jsou vsechny radky stejne dlouhe skoro zadarmo, kontrola jestli všechny okraje jsou zeď na 2 cykly. Protože máš okraje zeď tak nemusíš nic řešit a jen pustíš BFS. Lineárně s velikostí bludiště buď najdeš nejkratší cestu, anebo se ti vyprázdní fronta, pak cesta neexistuje.

A použít Dijkstru na graf, kde mají všechny hrany váhu 1, je taky hloupost.

To H4wk.cz : Mohl bys me vysvetlit, co presne je na tom nesmysl? Popsal sem slovne BFS a to je podle tebe spatne, protoze BFS je lepsi jak BFS?
A urcite je vytvoreni mapy v pohode? Mohl bys popsat nejaky jednoduchy algoritmus pro vytvareni?

To Krychlik : Takhle generuji já, je to docela jednoduché, takže nevím, s čím máš problém...
http://malyzelenyhnus.sweb.cz/bludiste.html

To Krychlik : Napsal jsi vlnka to nestihne. Tak teda nechápu co si představuješ pod pojmem vlnka. Taky jaká hranice pseudovlny? Snad si ve frontě pamatuju všechny nenavštívené sousedy a když žádný už nemám, tak konec. Narychlo jsem napsal načtení bludiště, kontroly jsou pak o tom to pole projít.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>



char **bludiste;



int main() {

    char *line = NULL;

    int n;



    int read = getline(&line, &n, stdin);

    int x = read, y = 100;

    bludiste = malloc(y * sizeof(char *));

    for (int i = 0; i < y; i++) {

        bludiste[i] = malloc(x+1);

    }

    strcpy(bludiste[0], line);



    int l = 1;

    while ((read = getline(&line, &n, stdin)) != -1) {

        if (read != x) {

            printf("Chyba.\n");

            return 1;

        }

        if (l == y) {

            bludiste = realloc(bludiste, (2*y)*sizeof(char *));

            y *= 2;

            for (int i = l; i < y; i++) {

                bludiste[i] = malloc(x+1);

            }

        }

        strcpy(bludiste[l], line);

        l++;

    }



    printf("\nTakhle vypada bludiste:\n");

    for (int i = 0; i < l; i++) {

        printf("%s", bludiste[i]);

    }



    printf("Bludiste ma rozmery: %dx%d", x-1, l);

}

To H4wk.cz : Jej sorry, s tim nacitanim sem se sek, nejak sem spatne precetl zadani, hlavne pasaz "Při realizaci je zakázáno používat C++ datový typ string" a nejak sem predpokladal, ze je zakazan i cstring a ze to tudiz bude potreba nacitat po jednotlivych znacich a pak to pokoutne nejak slepovat. Za toto se moc omlouvam.
Ale za druhou casti vyroku si stojim. Pod vlnkou si predstavuju uplne obycejnou vlnu (Polekrat projede cele pole). To je prvni hloupy napad. Ta by to nestihla, proto je lepsi BFS. Predpokladam ze tazatel ho nezna (Jinak by nezakladal toto vlakno) a link na wiki nemusi byt dostacujici. Proto sem se rozhodl ten algoritmus popsat. BFS si ve fronte pamatuje aktualni nenavstivene sousedy. Kdyz se nechaji vykreslit tak to bude "hranice vlny". Pri projiti vsech a pridani nenavstivenych sousedu a odstraneni aktualnich (presne jak to dela BFS) do/z fronty se tato hranice posune. To sem tim myslel. Pro predstavu je to dostacujici, podle tohoto popisu to dokaze kdokoliv naprogramovat a uveri ze to funguje. Ale priste radsi jenom poslu link na wiki bez popisu, at se s tim pekne potrapi ten, kdo se pta.

To Krychlik : Načítání beru, ale jinak se tu hádáme jen o termín. Já tvrdím, že Algoritmus vlny je jiný název pro BFS. Mám to podložené několika odkazy: http://ksvi.mff.cuni.cz/~kryl/Avyuka/20034/pozadPRG030.htm, http://kam.mff.cuni.cz/~kuba/ka/, http://www.kiv.zcu.cz/~konopik/sem/cech/index.html. Je od tebe hezké, že ses to snažil vysvětlit. Jen mi to vysvětlení přišlo tak chaotické, že jsem si to nedokázal představit :-) Pokud to ale pomohlo, tak proč ne. Já osobně nemám rád odpovědi RTFM :-)

To H4wk.cz : mas pravdu ze BFS je vyhledavani "sirky" tudiz se nejspis zacne na startu a prohledavaji se postupne vsechny okolni body, pak okolni body tech bodu .... jo zni to docela podobne jako vlnka :D

mimochodem trochu zrychlit by se to dalo i pouzitim hledani proti sobe... zacit ze startu i cile zaroven a pak jen hlidat jestli uz se nedostali na stejnou pozici (stejne se uz kontroluje zda se nevraci)

Souhlasim, ze se tu hadame o terminy, ale jeste k vlne. Existuje i hloupa a o te sem psal. Tak pro vsechny policka udela toto:
- je nejaky soused navstiveny? pokud ano, tak toto policko ma hodnotu (nejmensi z sousedu+1).
Toto se opakuje dokud cil nedostane hodnotu nebo se ten cyklus neudela polekrat. Pak se jenom vypise hodnota cile. Myslim, ze to je algoritmus, ktery cloveka, ktery nezna BFS, napadne jako prvni, da se napsat velmi jednoduse a rychle(< minutu) , take se mu da rikat vlna a je velmi pomaly. Kdezto BFS je uz ta chytra vlna. Proto sem napsal ze hloupa vlna to nestihne, je potreba chytra, a tu sem nejak popsal. No a protoze reakce na to byla "To jsou nesmysly, na tohle stačí BFS." tak sem se trosku nastval.

Zdravím,
ještě je v zadání, ža se mají řádky načítat pomocí fgets, testovat načtený řádek, buffer a konec zadávání vstupu feof(stdin). Zatim sem nejvíc času strávil nad tim načítánim a ukládánim do 2D pole, kde neznam počet řádků ani sloupců. Nevíte někdo jak nato? Je to docela záludný. Zkoušel sem třeba realloc a to se vzpouzí.

Dík.