labirint

labirint

offline
  • Davor 
  • Novi MyCity građanin
  • Pridružio: 19 Maj 2003
  • Poruke: 28
  • Gde živiš: Austrija

E ovako imam jedan problecic Smile

Treba mi pomoc u pronalazenju algoritma za pronalazak moguceg puta (mogucih puteva) u jednom labirintu. Znaci postoji labirint (matrica sa odredjenim brojem polja) koji ima jednu startnu i jednu ciljnu poziciju i slobodne elemente i elemente koji su zauzeti (zid). E sad, kako pronaci moguci put od starta do cilja.
Ima li neko ideju ?



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • mr_W 
  • Počasni građanin
  • Pridružio: 22 Mar 2004
  • Poruke: 835

A pretpostavljam da je u pitanju ili ispitni zadatak, ili nesto vrlo slicno tome ? Zbog cega ne procitas literaturu (udzbenike) ? Sigurno je tamo opisano... (a verovatno negde vec postoji gotovo resenje za zadato ispitno pitanje).

Sto se algoritma konkretno tice, probaj da celu situaciju postavis na papiru. Zatim analiziraj sebe kako resavas problem (labirint). Korak po korak. Tako ces dobiti barem neku pocetnu ideju.



offline
  • Davor 
  • Novi MyCity građanin
  • Pridružio: 19 Maj 2003
  • Poruke: 28
  • Gde živiš: Austrija

Jeste u pitanju zadatak, ali trazio sam na vise mjesta, nisam nista pronasao.
Google nije nista nasao Smile Sto se tice udzbenika hm... ovi sto imam (na njemackom) su pre opsirni a konkretno takav primjer nema u njima. Prof je misljenja da trebamo sami da osmislimo vecinu stvari, zato primjere koje zadaje ne stavlja u knjige, skrpite ....

Ima li neko tip gdje bi mogao naci slican primjer ?

offline
  • mr_W 
  • Počasni građanin
  • Pridružio: 22 Mar 2004
  • Poruke: 835

Davore,
zasto ne probas da resis problem sam ? Meni licno ne izgleda komplikovano. Istina da nikad nisam resavao te 'studentske' zadatke, ali imam tu-i-tamo nekog programerskog iskustva... koje mi govori to (-;

offline
  • Peca  Male
  • Glavni Administrator
  • Predrag Damnjanović
  • SysAdmin i programer
  • Pridružio: 17 Apr 2003
  • Poruke: 23072
  • Gde živiš: Niš

resenje - rekurzija!
dakle, da funkcija samu sebe poziva, sve dok ne pronadje ciljno polje.

odprilike ovako:
int trazi (int x, int y) // koordinate x,y {    if (da_li_sam_bio_ovde(x, y)==1) return 0;    if (da_li_je_zid(x,y)==1) return 0;    if (x==cilj_x && y==cilj_y)    {       nadjeno (x, y); // nasli smo       return 1;    }    // rekurzija    if (trazi (x+1, y)==1) return 1;    if (trazi (x-1, y)==1) return 1;    if (trazi (x, y+1)==1) return 1;    if (trazi (x, y-1)==1) return 1;    return 0; }

funkcija da_li_sam_bio_ovde() bi trebala da ima niz u koji bi upisivala koordinate u kojima je funkcija bila, i da tako proverava da li je funkcija vec bila na toj koordinati.

Eto, resen zadatak.
Mozda sam nesto ispustio iz vida, pa se funkcija nikad ne zaustavi Smile, mada... na prvi pogled bih rekao da je to to.

offline
  • Davor 
  • Novi MyCity građanin
  • Pridružio: 19 Maj 2003
  • Poruke: 28
  • Gde živiš: Austrija

Hm ok hvala pokusat cu da uradim nesto sa tim kodom.
Jos jedno pitanje :
map funkcija, funkcionise na principu key/value.
E sad, moze li se pod jednim key-om pohraniti vise razlicitih tipova value-a.
Znaci imam key 1 i 3 vrjednosti, jedna tipa string, druga int, treca char.
Postoji li takav Konstruktor u C++ -u?

offline
  • mr_W 
  • Počasni građanin
  • Pridružio: 22 Mar 2004
  • Poruke: 835

Naravno. Koristi strukturu za value:

struct myval {     std::string str;     int num;     char ch;   }; std::map<std::string, myval> mojamapa;

i onda mozes prilikom dodele da koristis:

mojamapa["kljuc"].str = "stringvrednost"; mojamapa["kljuc"].num = 123; mojamapa["kljuc"].ch = 'a';

ili dodela odjednom:

mojamapa["kljuc"] = (myval) { "string", 123, 'a' };

offline
  • Peca  Male
  • Glavni Administrator
  • Predrag Damnjanović
  • SysAdmin i programer
  • Pridružio: 17 Apr 2003
  • Poruke: 23072
  • Gde živiš: Niš

ako hoces u c++ stilu - onda umesto strukture napravi klasu Wink
prednost je velika... promenljive postaju objekti, koji imaju i svoje funkcije...

tu bi mogla da se napravi mreza objekata - svaka koordinata je jedan objekat - i onda objekti medjusobno 'reaguju'... recimo prenose 'impuls' sa sebe na susedne objekte, i tako nadjes put do ciljne koordinate Wink

offline
  • Pridružio: 01 Apr 2005
  • Poruke: 797
  • Gde živiš: Niš

Mrzelo me da citam sve predloge,ali ideja je da se "drzis jednom rukom(npr desnom) za zid" i do kraja pratis tu stranu.Trebalo bi da izadjes.

Ko je trenutno na forumu
 

Ukupno su 935 korisnika na forumu :: 29 registrovanih, 4 sakrivenih i 902 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3028 - dana 22 Nov 2019 07:47

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: AMCXXL, batofilm, caesar, dankisha, Drug pukovnik, duskovuk63, Fastdraw92, igorkozar83, indja, ivan979, ivance95, Kaplar2, Marko Marković, mihajlot2013, milandlc84.wow, milos.cbr, MiroslavD, npetrovic, Oluj2.1, s51o, sasakrajina, shone34, Skijavoneska, Sonyboy, Srednjoškolac u dilemi, vlvl, wolverined4, zlatkoa987, Zmaj 99