gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / PostojanjePuta / zad-put-u-lavirintu.txt
diff --git a/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt
--- /dev/null
@@ -0,0 +1,127 @@
+============================================================\r
+ Zadatak - pretrazivanje sa vracanjem - put u lavirintu\r
+============================================================\r
+\r
+\r
+Postavka problema\r
+============================================================\r
+\r
+Neka je dat lavirint kao matrica polja, pri cemu razlicite \r
+vrednosti polja imaju razlicito znacenje. Potrebno je pronaci\r
+put kroz lavirint od pocetnog polja, do izlaza iz lavirinta,\r
+pri cemu se pod putem smatra niz polja koja je potrebno \r
+posetiti u datom redosledu, da bi se stiglo od pocetnog polja\r
+do cilja. Pri obilasku lavirinta, sa jednog polja je moguce \r
+preci na susedno ako ona imaju istu ivicu, tj. ako se ono \r
+nalazi odmah levo, desno, gore ili dole u odnosu na trenutno \r
+polje.\r
+\r
+Znacenja vrednosti polja su;\r
+0 = slobodno polje u lavirintu na koje je dozvoljeno stati\r
+-11 = zid, polje na koje nije dozvoljeno stati\r
+-99 = izlaz iz lavirinta\r
+\r
+\r
+Format fajla\r
+------------------------------------------------------------\r
+\r
+Mapa je u fajlu predstavljena na sledeci nacin:\r
+\r
+U prvom redu se nalaze dva broja S i V koji predstavljaju\r
+sirinu i visinu mape.\r
+\r
+U sledecih V redova se nalaze po S celih brojeva koji\r
+predstavljaju vrednosti polja u lavirintu.\r
+\r
+Polje (0, 0) nalazi se u gornjem levom polju matrice.\r
+\r
+\r
+Primeri\r
+------------------------------------------------------------\r
+\r
+Za testiranje programa su dati su fajlovi:\r
+"lav1.txt" i "lav2.txt" u kojima postoji resenje\r
+"lavp.txt" koji ne sadrzi zidove\r
+"lavb.txt" u kojem nije moguce naci resenje\r
+\r
+"lav-rupe.txt" za testiranje modifikacije zadatka sa rupama\r
+"lav-prepreke.txt" za testiranje modifikacije zadatka sa preprekama\r
+\r
+Modifikacije su opisane na kraju teksta.\r
+\r
+\r
+Zadatak\r
+============================================================\r
+\r
+Napisati klasu LavirintProgram koja ucitava ime fajla u kojem\r
+se nalazi definisan lavirint, koordinate pocetne pozicije \r
+(x, y) od koje se trazi izlaz iz lavirinta, kao i izbor sta \r
+zelimo da radimo. Nakon ucitanog izbora, klasa treba da ucita\r
+lavirint iz datog fajla, ispise ga na ekran i izvrsi izabranu\r
+operaciju. \r
+\r
+Ponuditi korisniku sledeci izbor:\r
+1 - provera da li postoji put od unetog polja do izlaza\r
+2 - ispis puta ukoliko postoji, odnosno ispis poruke da put \r
+ ne postoji\r
+\r
+\r
+Pretrazivanje sa vracanjem\r
+------------------------------------------------------------\r
+\r
+Jedan od nacina da se uradi zadatak je koriscenjem pretrazivanja\r
+sa vracanjem (poznatom u literaturi pod engleskim nazivom\r
+"backtrack"). \r
+\r
+Ideja je jednostavna, krenemo od prvog polja, oznacimo ga\r
+kao poseceno i pokusamo da se prebacimo na bilo koje\r
+neobidjeno susedno. Na tom polju ponovimo isti postupak i\r
+tako nastavljamo dok ne naidjemo na izlaz ili dok vise\r
+nemamo gde da idemo. \r
+\r
+Ukoliko nismo naisli na izlaz, a nemamo gde dalje da idemo,\r
+onda oznacimo trenutno polje kao neobidjeno i vratimo se\r
+jedno polje nazad i probamo nekog drugog suseda. Ako vise\r
+nema suseda vratimo se jos jedno polje. Ukoliko vise nema\r
+gde da se vracamo znaci da se do izlaza ne moze doci.\r
+\r
+Backtrack je najlakse izvoditi rekurzivno, tako da se poziv\r
+procedure vrsi za pojedinacno polje. Ovako se povratkom iz\r
+rekurzije vracamo na polje odakle smo dosli.\r
+\r
+\r
+Jedna od mogucih varijanti ideje procedure:\r
+\r
+rek(i,j,...)\r
+- nije u matrici? -> izlaz\r
+- zid? -> izlaz\r
+- poseceno polje? -> izlaz\r
+- da li je kraj? -> obradimo resenje\r
+- inace trazimo dalje\r
+- postavimo da je poseceno polje\r
+- pokusamo da obidjemo sve susede:\r
+- rek(i+1,j,..)\r
+- rek(i-1,j,..)\r
+- rek(i,j+1,..)\r
+- rek(i,j-1,..)\r
+- postavimo da polje nije poseceno\r
+\r
+\r
+Prosirenje zadatka:\r
+------------------------------------------------------------ \r
+\r
+Neka je dat lavirint sa sledecim dodatnim poljima:\r
+-1 = rupa na putu\r
+bilo koji pozitivan broj = visina prepreke na putu\r
+\r
+Modifikovati postojece metode za trazenje puta tako da:\r
+- omogucavaju preskakanje rupa, ali samo ako je rupa velicine\r
+ jednog polja. Rupe koje su u datom pravcu duze od jednog \r
+ polja ne preskakati\r
+- omogucava penjanje po preprekama, ali samo po preprekama \r
+ koje su za najvise 3 vislje od visine trenutnog polja. \r
+ Ukoliko se vec nalazimo na prepreci, dozvoljeno je preci na\r
+ vislju prepreku, ukoliko ona nije veca za vise od 3 od \r
+ postojece prepreke. Silazak sa prepreke je moguc na bilo \r
+ koje polje osim zida\r
+- omogucava preskakanje prepreka, ali najvise 4 puta\r