PretrazivanjeSaVracanjem/Lavirint/Lavirint.java

   1 /**
   2  * Klasa Lavirint sadrzi 3 javne i tri privatne metode za trazenje puteva.
   3  *
   4  * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore
   5  * koji se korste pri trazenju najkraceg i najvrednijeg puta.
   6  */
   7
   8 import java.util.Comparator;
   9
  10 public class Lavirint {
  11
  12         // Polje m sadrzi kompletnu mapu
  13         private Mapa m;
  14         // Polje optResenje sluzi za pamcenje optimalnog resenja
  15         private Resenje optResenje;
  16
  17         // Ucitava mapu iz datog fajla i stampa je na ekran
  18         Lavirint(String imeFajla) {
  19                 m = Mapa.ucitajIzFajla(imeFajla);
  20                 m.stampaj();
  21         }
  22
  23         // Provarava da li postoji put do izlaza i vraca vrednost true
  24         // ako postoji put ili vrednost false ako ne postoji
  25         public boolean postojiPut(int x, int y) {
  26                 if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  27                         return false;
  28                 }
  29                 if (m.getPos(x, y) == true) {
  30                         return false;
  31                 }
  32                 if (m.getMat(x, y) == Mapa.ZID) {
  33                         return false;
  34                 }
  35                 if (m.getMat(x, y) == Mapa.IZLAZ) {
  36                         return true;
  37                 } else {
  38                         m.setPos(x, y, true);
  39                         if (postojiPut(x + 1, y)) {
  40                                 return true;
  41                         }
  42                         if (postojiPut(x - 1, y)) {
  43                                 return true;
  44                         }
  45                         if (postojiPut(x, y + 1)) {
  46                                 return true;
  47                         }
  48                         if (postojiPut(x, y - 1)) {
  49                                 return true;
  50                         }
  51                         m.setPos(x, y, false);
  52                         return false;
  53                 }
  54         }
  55
  56         // Poziva metodu rput da pronadje i ispise put, ako postoji
  57         // Ukoliko put ne postoji, ispisuje poruku o gresci
  58         public void nadjiPut(int x, int y) {
  59                 if (!rput(x, y)) {
  60                         System.err.println("Ne postoji put");
  61                 }
  62         }
  63
  64         // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
  65         // Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom
  66         // redosledu
  67         // Put se stampa pri povratku iz rekurzije
  68         private boolean rput(int x, int y) {
  69                 if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  70                         return false;
  71                 }
  72                 if (m.getPos(x, y)) {
  73                         return false;
  74                 }
  75                 if (m.getMat(x, y) == Mapa.ZID) {
  76                         return false;
  77                 }
  78                 if (m.getMat(x, y) == Mapa.IZLAZ) {
  79                         System.out.println(x + " " + y);
  80                         return true;
  81                 } else {
  82                         m.setPos(x, y, true);
  83                         if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)
  84                                         || rput(x - 1, y)) {
  85                                 System.out.println(x + " " + y);
  86                                 return true;
  87                         }
  88                         m.setPos(x, y, false);
  89                         return false;
  90                 }
  91         }
  92
  93         // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
  94         // koristi komparator po duzini resenja, tj. trazi se najkrace resenje
  95         // Samo resenje kreira se u metodi optPut
  96         public Resenje najkraciPut(int x, int y) {
  97                 Resenje r = new Resenje();
  98                 optPut(x, y, r, new KomparatorPoDuzini());
  99                 return optResenje;
 100         }
 101
 102         // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
 103         // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje
 104         // Samo resenje kreira se u metodi optPut
 105         public Resenje najvrednijiPut(int x, int y) {
 106                 Resenje r = new Resenje();
 107                 optPut(x, y, r, new KomparatorPoVredosti());
 108                 return optResenje;
 109         }
 110
 111         // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
 112         // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u
 113         // optResenje
 114         // Optimalnost resenja se proverava komparatorom
 115         private void optPut(int x, int y, Resenje r, Comparator<Resenje> c) {
 116                 if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
 117                         return;
 118                 }
 119                 if (m.getPos(x, y)) {
 120                         return;
 121                 }
 122                 if (m.getMat(x, y) == Mapa.ZID) {
 123                         return;
 124                 }
 125                 if (m.getMat(x, y) == Mapa.IZLAZ) {
 126                         r.dodaj(x, y, 0);
 127                         if (optResenje == null || c.compare(r, optResenje) < 0) {
 128                                 optResenje = r.clone();
 129                         }
 130                         r.izbaciKraj();
 131                 } else {
 132                         m.setPos(x, y, true);
 133                         r.dodaj(x, y, m.getMat(x, y));
 134                         optPut(x + 1, y, r, c);
 135                         optPut(x, y + 1, r, c);
 136                         optPut(x, y - 1, r, c);
 137                         optPut(x - 1, y, r, c);
 138                         m.setPos(x, y, false);
 139                         r.izbaciKraj();
 140                 }
 141         }
 142 }
 143
 144 // Komparator za resenja po duzini resenja
 145 class KomparatorPoDuzini implements Comparator<Resenje> {
 146         public int compare(Resenje r1, Resenje r2) {
 147                 return r1.getLength() - r2.getLength();
 148         }
 149 }
 150
 151 // Komparator za resenja po vrednosti resenja
 152 class KomparatorPoVredosti implements Comparator<Resenje> {
 153         public int compare(Resenje r1, Resenje r2) {
 154                 return r2.getVrednost() - r1.getVrednost();
 155         }
 156 }