PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/zadatak-lavirint.txt

   1 Zadatak - pretrazivanje sa vracanjem - lavirint
   2 ============================================================
   3
   4 Napisati program koji ucitava lavirint iz fajla i nalazi put
   5 ili puteve sa odredjenim osobinama.
   6
   7
   8 Format fajla
   9 ------------------------------------------------------------
  10
  11 Lavirint je u fajlu predstavljen na sledeci nacin:
  12
  13 U prvom redu se nalaze dva broja S i V (1<= S, V <=10), koji
  14 predstavljaju sirinu i visinu lavirinta. U sledecih V redova
  15 se nalaze po S celih brojeva koji predstavljaju lavirint.
  16 Brojevi imaju sledece znacenje:
  17
  18  0 - prazno polje
  19 -1 - zid, na ovo polje se ne moze stupiti
  20 -5 - izlaz iz lavirinta
  21
  22 Sa jednog polja se moze preci na drugo, ukoliko imaju
  23 zajednicku stranicu, odnosno mozemo preci na polje levo,
  24 desno, gore ili dole.
  25
  26 Pri ucitavanju pretpostaviti da ukoliko fajl postoji da su
  27 podaci u njemu ispravno zadati.
  28
  29
  30 Zadatak
  31 ------------------------------------------------------------
  32
  33 - Napisati program tako da proverava da li postoji put od
  34 pocetnog polja do izlaza iz lavirinta. Pocetno polje je na
  35 koordinatama 1,1, odnosno u gornjem levom uglu.
  36
  37 - Program prosiriti tako da na ekran ispisuje trazeni put
  38 (ako postoji).
  39
  40 - Modifikovati program tako da vraca najkraci put do
  41 izlaza.
  42
  43 - Razmotriti sledecu modifikaciju problema:
  44
  45 U drevnim lavirintima se nalaze zlatnici razasuti po
  46 poljima. Ovi lavirinti su veoma opasni, pa ih nije
  47 jednostavno pokupiti, vec se to moze raditi samo pomocu
  48 specijalnih robota. Na srecu pronadjene su mape koje
  49 precizno pokazuju kako lavirinti izgledaju, gde su im izlazi
  50 i koliko zlatnika se moze pokupiti na kom polju. Sada treba
  51 naci put kroz lavirint tako da se pokupi sto vise zlatnika,
  52 a da se pri tome ne nagazi na isto polje dva puta.
  53
  54 Pri ucitavanju lavirinta, bilo koji pozitivan broj
  55 predstavlja broj zlatnika na tom polju. Program treba da
  56 vraca optimalni put do izlaza, odnosno takav da se pokupi
  57 sto vise zlatnika na putu.