PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/LavirintV2.java

   1 /**
   2  * Klasa Lavirint sadrzi 2 javne i jednu privatnu metodu 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 LavirintV2 {
  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  LavirintV2(String imeFajla) {
  19   m = Mapa.ucitajIzFajla(imeFajla);
  20   m.stampaj();
  21  }
  22
  23  // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
  24  // koristi komparator po duzini resenja, tj. trazi se najkrace resenje
  25  // Samo resenje kreira se u metodi optPut
  26  public Resenje najkraciPut(int x, int y) {
  27   Resenje r = new Resenje();
  28   optPut(x, y, r, new KomparatorPoDuzini());
  29   return optResenje;
  30  }
  31
  32  // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
  33  // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje
  34  // Samo resenje kreira se u metodi optPut
  35  public Resenje najvrednijiPut(int x, int y) {
  36   Resenje r = new Resenje();
  37   optPut(x, y, r, new KomparatorPoVredosti());
  38   return optResenje;
  39  }
  40
  41  // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
  42  // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u
  43  // optResenje
  44  // Optimalnost resenja se proverava komparatorom
  45  private void optPut(int x, int y, Resenje r, Comparator<Resenje> c) {
  46   if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  47    return;
  48   }
  49   if (m.getPos(x, y)) {
  50    return;
  51   }
  52   if (m.getMat(x, y) == Mapa.ZID) {
  53    return;
  54   }
  55   if (m.getMat(x, y) == Mapa.IZLAZ) {
  56    r.dodaj(x, y, 0);
  57    if (optResenje == null || c.compare(r, optResenje) < 0) {
  58     optResenje = r.clone();
  59    }
  60    r.izbaciKraj();
  61   } else {
  62    m.setPos(x, y, true);
  63    r.dodaj(x, y, m.getMat(x, y));
  64    optPut(x + 1, y, r, c);
  65    optPut(x, y + 1, r, c);
  66    optPut(x, y - 1, r, c);
  67    optPut(x - 1, y, r, c);
  68    m.setPos(x, y, false);
  69    r.izbaciKraj();
  70   }
  71  }
  72 }
  73
  74 // Komparator za resenja po duzini resenja
  75 class KomparatorPoDuzini implements Comparator<Resenje> {
  76  public int compare(Resenje r1, Resenje r2) {
  77   return r1.getLength() - r2.getLength();
  78  }
  79 }
  80
  81 // Komparator za resenja po vrednosti resenja
  82 class KomparatorPoVredosti implements Comparator<Resenje> {
  83  public int compare(Resenje r1, Resenje r2) {
  84   return r2.getVrednost() - r1.getVrednost();
  85  }
  86 }