PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/zad-put-u-lavirintu.txt

   1 ============================================================
   2   Zadatak - pretrazivanje sa vracanjem - put u lavirintu
   3 ============================================================
   4
   5
   6 Postavka problema
   7 ============================================================
   8
   9 Neka je dat lavirint kao matrica polja, pri cemu razlicite
  10 vrednosti polja imaju razlicito znacenje. Potrebno je pronaci
  11 put kroz lavirint od pocetnog polja, do izlaza iz lavirinta,
  12 pri cemu se pod putem smatra niz polja koja je potrebno
  13 posetiti u datom redosledu, da bi se stiglo od pocetnog polja
  14 do cilja. Pri obilasku lavirinta, sa jednog polja je moguce
  15 preci na susedno ako ona imaju istu ivicu, tj. ako se ono
  16 nalazi odmah levo, desno, gore ili dole u odnosu na trenutno
  17 polje.
  18
  19 Znacenja vrednosti polja su;
  20 0   = slobodno polje u lavirintu na koje je dozvoljeno stati
  21 -11 = zid, polje na koje nije dozvoljeno stati
  22 -99 = izlaz iz lavirinta
  23
  24
  25 Format fajla
  26 ------------------------------------------------------------
  27
  28 Mapa je u fajlu predstavljena na sledeci nacin:
  29
  30 U prvom redu se nalaze dva broja S i V koji predstavljaju
  31 sirinu i visinu mape.
  32
  33 U sledecih V redova se nalaze po S celih brojeva koji
  34 predstavljaju vrednosti polja u lavirintu.
  35
  36 Polje (0, 0) nalazi se u gornjem levom polju matrice.
  37
  38
  39 Primeri
  40 ------------------------------------------------------------
  41
  42 Za testiranje programa su dati su fajlovi:
  43 "lav1.txt" i "lav2.txt" u kojima postoji resenje
  44 "lavp.txt" koji ne sadrzi zidove
  45 "lavb.txt" u kojem nije moguce naci resenje
  46
  47 "lav-rupe.txt" za testiranje modifikacije zadatka sa rupama
  48 "lav-prepreke.txt" za testiranje modifikacije zadatka sa preprekama
  49
  50 Modifikacije su opisane na kraju teksta.
  51
  52
  53 Zadatak
  54 ============================================================
  55
  56 Napisati klasu PostojanjePuta koja ucitava ime fajla u kojem
  57 se nalazi definisan lavirint. Program treba da ucita
  58 lavirint iz datog fajla, ispise ga na ekran i proveri
  59 postojanje puta.
  60
  61 Uzeti da je pocetno polje uvek 0,0, odnosno gornji levi
  62 ugao.
  63
  64
  65 Pretrazivanje sa vracanjem
  66 ------------------------------------------------------------
  67
  68 Jedan od nacina da se uradi zadatak je koriscenjem
  69 pretrazivanja sa vracanjem (poznatom u literaturi pod
  70 engleskim nazivom "backtrack").
  71
  72 Ideja je jednostavna, krenemo od prvog polja, oznacimo ga
  73 kao poseceno i pokusamo da se prebacimo na bilo koje
  74 neobidjeno susedno. Na tom polju ponovimo isti postupak i
  75 tako nastavljamo dok ne naidjemo na izlaz ili dok vise
  76 nemamo gde da idemo.
  77
  78 Ukoliko nismo naisli na izlaz, a nemamo gde dalje da idemo,
  79 onda oznacimo trenutno polje kao neobidjeno i vratimo se
  80 jedno polje nazad i probamo nekog drugog suseda. Ako vise
  81 nema suseda vratimo se jos jedno polje. Ukoliko vise nema
  82 gde da se vracamo znaci da se do izlaza ne moze doci.
  83
  84 Backtrack je najlakse izvoditi rekurzivno, tako da se poziv
  85 procedure vrsi za pojedinacno polje. Ovako se povratkom iz
  86 rekurzije vracamo na polje odakle smo dosli.
  87
  88 Jedna od mogucih varijanti ideje procedure:
  89
  90 rek(i,j,...)
  91 - nije u matrici?  -> izlaz
  92 - zid?  -> izlaz
  93 - poseceno polje? -> izlaz
  94 - da li je kraj? -> obradimo resenje
  95 - inace trazimo dalje
  96 -   postavimo da je poseceno polje
  97 -   pokusamo da obidjemo sve susede:
  98 -       rek(i+1,j,..)
  99 -       rek(i-1,j,..)
 100 -       rek(i,j+1,..)
 101 -       rek(i,j-1,..)
 102 -   postavimo da polje nije poseceno
 103
 104
 105 Prosirenje zadatka:
 106 ------------------------------------------------------------
 107
 108 Dodati da se korisnik pita za pocetno polje u lavirintu
 109 umesto da se uvek koristi 0,0.
 110
 111 Dodati da se ispise nadjeni put u lavirintu (u sustini je
 112 dosta pri povratku iz rekurzije ispisivati polja koja
 113 su vratila true).
 114
 115 Neka je dat lavirint sa sledecim dodatnim poljima:
 116 -1 = rupa na putu
 117 bilo koji pozitivan broj = visina prepreke na putu
 118
 119 Modifikovati postojece metode za trazenje puta tako da:
 120 - omogucavaju preskakanje rupa, ali samo ako je rupa velicine
 121   jednog polja. Rupe koje su u datom pravcu duze od jednog
 122   polja ne preskakati
 123 - omogucava penjanje po preprekama, ali samo po preprekama
 124   koje su za najvise 3 vislje od visine trenutnog polja.
 125   Ukoliko se vec nalazimo na prepreci, dozvoljeno je preci na
 126   vislju prepreku, ukoliko ona nije veca za vise od 3 od
 127   postojece prepreke. Silazak sa prepreke je moguc na bilo
 128   koje polje osim zida
 129 - omogucava preskakanje prepreka, ali najvise 4 puta