gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / SuperKomplikovanoResenje / zadatak-lavirint.txt
diff --git a/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/zadatak-lavirint.txt b/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/zadatak-lavirint.txt
--- /dev/null
@@ -0,0 +1,57 @@
+Zadatak - pretrazivanje sa vracanjem - lavirint\r
+============================================================\r
+\r
+Napisati program koji ucitava lavirint iz fajla i nalazi put\r
+ili puteve sa odredjenim osobinama.\r
+\r
+\r
+Format fajla\r
+------------------------------------------------------------\r
+\r
+Lavirint je u fajlu predstavljen na sledeci nacin:\r
+\r
+U prvom redu se nalaze dva broja S i V (1<= S, V <=10), koji\r
+predstavljaju sirinu i visinu lavirinta. U sledecih V redova\r
+se nalaze po S celih brojeva koji predstavljaju lavirint.\r
+Brojevi imaju sledece znacenje:\r
+\r
+ 0 - prazno polje\r
+-1 - zid, na ovo polje se ne moze stupiti\r
+-5 - izlaz iz lavirinta\r
+\r
+Sa jednog polja se moze preci na drugo, ukoliko imaju\r
+zajednicku stranicu, odnosno mozemo preci na polje levo,\r
+desno, gore ili dole.\r
+\r
+Pri ucitavanju pretpostaviti da ukoliko fajl postoji da su\r
+podaci u njemu ispravno zadati.\r
+\r
+\r
+Zadatak\r
+------------------------------------------------------------\r
+\r
+- Napisati program tako da proverava da li postoji put od\r
+pocetnog polja do izlaza iz lavirinta. Pocetno polje je na\r
+koordinatama 1,1, odnosno u gornjem levom uglu.\r
+\r
+- Program prosiriti tako da na ekran ispisuje trazeni put\r
+(ako postoji).\r
+\r
+- Modifikovati program tako da vraca najkraci put do\r
+izlaza.\r
+\r
+- Razmotriti sledecu modifikaciju problema: \r
+\r
+U drevnim lavirintima se nalaze zlatnici razasuti po\r
+poljima. Ovi lavirinti su veoma opasni, pa ih nije\r
+jednostavno pokupiti, vec se to moze raditi samo pomocu\r
+specijalnih robota. Na srecu pronadjene su mape koje\r
+precizno pokazuju kako lavirinti izgledaju, gde su im izlazi\r
+i koliko zlatnika se moze pokupiti na kom polju. Sada treba\r
+naci put kroz lavirint tako da se pokupi sto vise zlatnika,\r
+a da se pri tome ne nagazi na isto polje dva puta.\r
+\r
+Pri ucitavanju lavirinta, bilo koji pozitivan broj\r
+predstavlja broj zlatnika na tom polju. Program treba da\r
+vraca optimalni put do izlaza, odnosno takav da se pokupi\r
+sto vise zlatnika na putu.\r