labirint

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

E ovako imam jedan problecic

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 ?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Jeste u pitanju zadatak, ali trazio sam na vise mjesta, nisam nista pronasao.
Google nije nista nasao 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 ?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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 (-;

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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

odprilike ovako:

0. int trazi (int x, int y) // koordinate x,y
1. {
2.    if (da_li_sam_bio_ovde(x, y)==1) return 0;
3.    if (da_li_je_zid(x,y)==1) return 0;
4.  
5.    if (x==cilj_x && y==cilj_y)
6.    {
7.       nadjeno (x, y); // nasli smo
8.       return 1;
9.    }
10.  
11.    // rekurzija
12.    if (trazi (x+1, y)==1) return 1;
13.    if (trazi (x-1, y)==1) return 1;
14.    if (trazi (x, y+1)==1) return 1;
15.    if (trazi (x, y-1)==1) return 1;
16.  
17.    return 0;
18. }

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Naravno. Koristi strukturu za value:

0. struct myval {
1.     std::string str;
2.     int num;
3.     char ch;
4.   };
5.  
6. std::map<std::string, myval> mojamapa;

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

ako hoces u c++ stilu - onda umesto strukture napravi klasu
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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.