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
-============================================================\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 PostojanjePuta koja ucitava ime fajla u kojem\r
-se nalazi definisan lavirint. Program treba da ucita\r
-lavirint iz datog fajla, ispise ga na ekran i proveri\r
-postojanje puta.\r
-\r
-Uzeti da je pocetno polje uvek 0,0, odnosno gornji levi\r
-ugao.\r
-\r
-\r
-Pretrazivanje sa vracanjem\r
-------------------------------------------------------------\r
-\r
-Jedan od nacina da se uradi zadatak je koriscenjem\r
-pretrazivanja sa vracanjem (poznatom u literaturi pod\r
-engleskim nazivom "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
-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
-Dodati da se korisnik pita za pocetno polje u lavirintu\r
-umesto da se uvek koristi 0,0.\r
-\r
-Dodati da se ispise nadjeni put u lavirintu (u sustini je\r
-dosta pri povratku iz rekurzije ispisivati polja koja\r
-su vratila true).\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
+============================================================
+ Zadatak - pretrazivanje sa vracanjem - put u lavirintu
+============================================================
+
+
+Postavka problema
+============================================================
+
+Neka je dat lavirint kao matrica polja, pri cemu razlicite
+vrednosti polja imaju razlicito znacenje. Potrebno je pronaci
+put kroz lavirint od pocetnog polja, do izlaza iz lavirinta,
+pri cemu se pod putem smatra niz polja koja je potrebno
+posetiti u datom redosledu, da bi se stiglo od pocetnog polja
+do cilja. Pri obilasku lavirinta, sa jednog polja je moguce
+preci na susedno ako ona imaju istu ivicu, tj. ako se ono
+nalazi odmah levo, desno, gore ili dole u odnosu na trenutno
+polje.
+
+Znacenja vrednosti polja su;
+0 = slobodno polje u lavirintu na koje je dozvoljeno stati
+-11 = zid, polje na koje nije dozvoljeno stati
+-99 = izlaz iz lavirinta
+
+
+Format fajla
+------------------------------------------------------------
+
+Mapa je u fajlu predstavljena na sledeci nacin:
+
+U prvom redu se nalaze dva broja S i V koji predstavljaju
+sirinu i visinu mape.
+
+U sledecih V redova se nalaze po S celih brojeva koji
+predstavljaju vrednosti polja u lavirintu.
+
+Polje (0, 0) nalazi se u gornjem levom polju matrice.
+
+
+Primeri
+------------------------------------------------------------
+
+Za testiranje programa su dati su fajlovi:
+"lav1.txt" i "lav2.txt" u kojima postoji resenje
+"lavp.txt" koji ne sadrzi zidove
+"lavb.txt" u kojem nije moguce naci resenje
+
+"lav-rupe.txt" za testiranje modifikacije zadatka sa rupama
+"lav-prepreke.txt" za testiranje modifikacije zadatka sa preprekama
+
+Modifikacije su opisane na kraju teksta.
+
+
+Zadatak
+============================================================
+
+Napisati klasu PostojanjePuta koja ucitava ime fajla u kojem
+se nalazi definisan lavirint. Program treba da ucita
+lavirint iz datog fajla, ispise ga na ekran i proveri
+postojanje puta.
+
+Uzeti da je pocetno polje uvek 0,0, odnosno gornji levi
+ugao.
+
+
+Pretrazivanje sa vracanjem
+------------------------------------------------------------
+
+Jedan od nacina da se uradi zadatak je koriscenjem
+pretrazivanja sa vracanjem (poznatom u literaturi pod
+engleskim nazivom "backtrack").
+
+Ideja je jednostavna, krenemo od prvog polja, oznacimo ga
+kao poseceno i pokusamo da se prebacimo na bilo koje
+neobidjeno susedno. Na tom polju ponovimo isti postupak i
+tako nastavljamo dok ne naidjemo na izlaz ili dok vise
+nemamo gde da idemo.
+
+Ukoliko nismo naisli na izlaz, a nemamo gde dalje da idemo,
+onda oznacimo trenutno polje kao neobidjeno i vratimo se
+jedno polje nazad i probamo nekog drugog suseda. Ako vise
+nema suseda vratimo se jos jedno polje. Ukoliko vise nema
+gde da se vracamo znaci da se do izlaza ne moze doci.
+
+Backtrack je najlakse izvoditi rekurzivno, tako da se poziv
+procedure vrsi za pojedinacno polje. Ovako se povratkom iz
+rekurzije vracamo na polje odakle smo dosli.
+
+Jedna od mogucih varijanti ideje procedure:
+
+rek(i,j,...)
+- nije u matrici? -> izlaz
+- zid? -> izlaz
+- poseceno polje? -> izlaz
+- da li je kraj? -> obradimo resenje
+- inace trazimo dalje
+- postavimo da je poseceno polje
+- pokusamo da obidjemo sve susede:
+- rek(i+1,j,..)
+- rek(i-1,j,..)
+- rek(i,j+1,..)
+- rek(i,j-1,..)
+- postavimo da polje nije poseceno
+
+
+Prosirenje zadatka:
+------------------------------------------------------------
+
+Dodati da se korisnik pita za pocetno polje u lavirintu
+umesto da se uvek koristi 0,0.
+
+Dodati da se ispise nadjeni put u lavirintu (u sustini je
+dosta pri povratku iz rekurzije ispisivati polja koja
+su vratila true).
+
+Neka je dat lavirint sa sledecim dodatnim poljima:
+-1 = rupa na putu
+bilo koji pozitivan broj = visina prepreke na putu
+
+Modifikovati postojece metode za trazenje puta tako da:
+- omogucavaju preskakanje rupa, ali samo ako je rupa velicine
+ jednog polja. Rupe koje su u datom pravcu duze od jednog
+ polja ne preskakati
+- omogucava penjanje po preprekama, ali samo po preprekama
+ koje su za najvise 3 vislje od visine trenutnog polja.
+ Ukoliko se vec nalazimo na prepreci, dozvoljeno je preci na
+ vislju prepreku, ukoliko ona nije veca za vise od 3 od
+ postojece prepreke. Silazak sa prepreke je moguc na bilo
+ koje polje osim zida
+- omogucava preskakanje prepreka, ali najvise 4 puta