PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/Lavirint.java

   1 /**
   2  * Klasa Lavirint sadrzi 2 javne i jednu privatnu metodu za trazenje puteva.
   3  *
   4  */
   5
   6 public class Lavirint {
   7
   8  // Polje m sadrzi kompletnu mapu
   9  private Mapa m;
  10
  11  // Ucitava mapu iz datog fajla i stampa je na ekran
  12  Lavirint(String imeFajla) {
  13   m = Mapa.ucitajIzFajla(imeFajla);
  14   m.stampaj();
  15  }
  16
  17  // Provarava da li postoji put do izlaza i vraca vrednost true
  18  // ako postoji put ili vrednost false ako ne postoji
  19  public boolean postojiPut(int x, int y) {
  20   if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  21    return false;
  22   }
  23   if (m.getPos(x, y) == true) {
  24    return false;
  25   }
  26   if (m.getMat(x, y) == Mapa.ZID) {
  27    return false;
  28   }
  29   if (m.getMat(x, y) == Mapa.IZLAZ) {
  30    return true;
  31   } else {
  32    m.setPos(x, y, true);
  33    if (postojiPut(x + 1, y)) {
  34     return true;
  35    }
  36    if (postojiPut(x - 1, y)) {
  37     return true;
  38    }
  39    if (postojiPut(x, y + 1)) {
  40     return true;
  41    }
  42    if (postojiPut(x, y - 1)) {
  43     return true;
  44    }
  45    m.setPos(x, y, false);
  46    return false;
  47   }
  48  }
  49
  50  // Poziva metodu rput da pronadje i ispise put, ako postoji
  51  // Ukoliko put ne postoji, ispisuje poruku o gresci
  52  public void nadjiPut(int x, int y) {
  53   if (!rput(x, y)) {
  54    System.err.println("Ne postoji put");
  55   }
  56  }
  57
  58  // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
  59  // Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom
  60  // redosledu
  61  // Put se stampa pri povratku iz rekurzije
  62  private boolean rput(int x, int y) {
  63   if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
  64    return false;
  65   }
  66   if (m.getPos(x, y)) {
  67    return false;
  68   }
  69   if (m.getMat(x, y) == Mapa.ZID) {
  70    return false;
  71   }
  72   if (m.getMat(x, y) == Mapa.IZLAZ) {
  73    System.out.println(x + " " + y);
  74    return true;
  75   } else {
  76    m.setPos(x, y, true);
  77    if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)
  78      || rput(x - 1, y)) {
  79     System.out.println(x + " " + y);
  80     return true;
  81    }
  82    m.setPos(x, y, false);
  83    return false;
  84   }
  85  }
  86 }