Pomoc s Ukolem v C za penezni odmenu!!!! – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

16. 12. 2009   #1
-
0
-

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!!!

Nahlásit jako SPAM
IP: 90.177.136.–
Anonymní uživatel
~ Anonymní uživatel
0 příspěvků
17. 12. 2009   #2
-
0
-

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

Nahlásit jako SPAM
IP: 147.251.51.–
midin0
Věrný člen
17. 12. 2009   #3
-
0
-

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

Nahlásit jako SPAM
IP: 90.177.64.–
Zápisky z dění na FB (momentálně ve vývoji): http://fbpd.ic.cz/
sputnikone+1
Věrný člen
17. 12. 2009   #4
-
0
-

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

Nahlásit jako SPAM
IP: 147.251.201.–
reciproke
~ Anonymní uživatel
98 příspěvků
17. 12. 2009   #5
-
0
-

to smrdí ProgTestem

Nahlásit jako SPAM
IP: 213.194.242.–
D-Fox0
Stálý člen
17. 12. 2009   #6
-
0
-

Progtest to je na 100% :)

Nahlásit jako SPAM
IP: 213.220.207.–
Krychlik
~ Anonymní uživatel
195 příspěvků
17. 12. 2009   #7
-
0
-

"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 :-)

Nahlásit jako SPAM
IP: 195.113.15.–
Grungy0
Super člen
17. 12. 2009   #8
-
0
-

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

Nahlásit jako SPAM
IP: 158.193.84.–
Prvý náznak hlúposti, je pocit geniality.
H4wk.cz0
Newbie
17. 12. 2009   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 78.128.196.–
http://ksp.mff.cuni.cz - Nauč se opravdu programovat
Krychlik
~ Anonymní uživatel
195 příspěvků
18. 12. 2009   #10
-
0
-

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?

Nahlásit jako SPAM
IP: 195.113.15.–
sputnikone+1
Věrný člen
18. 12. 2009   #11
-
0
-
Nahlásit jako SPAM
IP: 89.176.157.–
H4wk.cz0
Newbie
18. 12. 2009   #12
-
0
-

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);
}

Nahlásit jako SPAM
IP: 78.128.196.–
http://ksp.mff.cuni.cz - Nauč se opravdu programovat
Krychlik
~ Anonymní uživatel
195 příspěvků
18. 12. 2009   #13
-
0
-

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.

Nahlásit jako SPAM
IP: 195.113.15.–
H4wk.cz0
Newbie
19. 12. 2009   #14
-
0
-

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 :-)

Nahlásit jako SPAM
IP: 78.128.196.–
http://ksp.mff.cuni.cz - Nauč se opravdu programovat
KIIV
~ Moderátor
+43
God of flame
19. 12. 2009   #15
-
0
-

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)

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Krychlik
~ Anonymní uživatel
195 příspěvků
19. 12. 2009   #16
-
0
-

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.

Nahlásit jako SPAM
IP: 195.113.15.–
tokányi
~ Anonymní uživatel
1 příspěvek
25. 12. 2009   #17
-
0
-

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.

Nahlásit jako SPAM
IP: 217.75.216.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 72 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý