PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/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 = new Mapa(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                 }
  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         // Poziva metodu rput da pronadje i ispise put, ako postoji
  56         // Ukoliko put ne postoji, ispisuje poruku o gresci
  57         public void nadjiPut(int x, int y) {
  58                 if (!rput(x, y)) {
  59                         System.err.println("Ne postoji put");
  60                 }
  61         }
  62
  63         // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
  64         // Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom
  65         // redosledu
  66         // Put se stampa pri povratku iz rekurzije
  67         private boolean rput(int x, int y) {
  68                 if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  69                         return false;
  70                 }
  71                 if (m.getPos(x, y)) {
  72                         return false;
  73                 }
  74                 if (m.getMat(x, y) == Mapa.ZID) {
  75                         return false;
  76                 }
  77                 if (m.getMat(x, y) == Mapa.IZLAZ) {
  78                         System.out.println(x + " " + y);
  79                         return true;
  80                 }
  81                 m.setPos(x, y, true);
  82                 if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)
  83                                 || rput(x - 1, y)) {
  84                         System.out.println(x + " " + y);
  85                         return true;
  86                 }
  87                 m.setPos(x, y, false);
  88                 return false;
  89         }
  90
  91         // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
  92         // koristi komparator po duzini resenja, tj. trazi se najkrace resenje
  93         // Samo resenje kreira se u metodi optPut
  94         public Resenje najkraciPut(int x, int y) {
  95                 Resenje r = new Resenje();
  96                 optPut(x, y, r, new KomparatorPoDuzini());
  97                 return optResenje;
  98         }
  99
 100         // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
 101         // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje
 102         // Samo resenje kreira se u metodi optPut
 103         public Resenje najvrednijiPut(int x, int y) {
 104                 Resenje r = new Resenje();
 105                 optPut(x, y, r, new KomparatorPoVredosti());
 106                 return optResenje;
 107         }
 108
 109         // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
 110         // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u
 111         // optResenje
 112         // Optimalnost resenja se proverava komparatorom
 113         private void optPut(int x, int y, Resenje r, Comparator<Resenje> c) {
 114                 if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
 115                         return;
 116                 }
 117                 if (m.getPos(x, y)) {
 118                         return;
 119                 }
 120                 if (m.getMat(x, y) == Mapa.ZID) {
 121                         return;
 122                 }
 123                 if (m.getMat(x, y) == Mapa.IZLAZ) {
 124                         r.dodaj(x, y, 0);
 125                         if (optResenje == null || c.compare(r, optResenje) < 0) {
 126                                 optResenje = new Resenje(r);
 127                         }
 128                         r.izbaciKraj();
 129                         return;
 130                 }
 131
 132                 // pokusavamo da trazimo dalje put
 133                 m.setPos(x, y, true);
 134                 r.dodaj(x, y, m.getMat(x, y));
 135                 optPut(x + 1, y, r, c);
 136                 optPut(x, y + 1, r, c);
 137                 optPut(x, y - 1, r, c);
 138                 optPut(x - 1, y, r, c);
 139                 m.setPos(x, y, false);
 140                 r.izbaciKraj();
 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 }