X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=blobdiff_plain;f=PretrazivanjeSaVracanjem%2FLavirint%2FSuperKomplikovanoResenje%2FLavirint.java;fp=PretrazivanjeSaVracanjem%2FLavirint%2FSuperKomplikovanoResenje%2FLavirint.java;h=5b84e5adfddf7d0207d7c8a90d54dd6bb8ebc2ee;hp=0000000000000000000000000000000000000000;hb=548ea5272576d592053c4e99f512b2fadc1053f7;hpb=1b832014e4d2d31b2502f4688623140d722005b1

diff --git a/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/Lavirint.java
new file mode 100644
index 0000000..5b84e5a
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/Lavirint.java
@@ -0,0 +1,156 @@
+import java.util.Comparator;
+
+/**
+ * Klasa Lavirint sadrzi 3 javne i tri privatne metode za trazenje puteva.
+ *
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.
+ */
+public class Lavirint {
+
+	// Polje m sadrzi kompletnu mapu
+	private Mapa m;
+
+	// Polje optResenje sluzi za pamcenje optimalnog resenja
+	private Put optResenje;
+
+	// Ucitava mapu iz datog fajla i stampa je na ekran
+	Lavirint(String imeFajla) {
+		m = new Mapa(imeFajla);
+		m.stampaj();
+	}
+
+	// Provarava da li postoji put do izlaza i vraca vrednost true
+	// ako postoji put ili vrednost false ako ne postoji
+	public boolean postojiPut(int x, int y) {
+		if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
+			return false;
+		}
+		if (m.getPos(x, y) == true) {
+			return false;
+		}
+		if (m.getMat(x, y) == Mapa.ZID) {
+			return false;
+		}
+		if (m.getMat(x, y) == Mapa.IZLAZ) {
+			return true;
+		}
+		m.setPos(x, y, true);
+		if (postojiPut(x + 1, y)) {
+			return true;
+		}
+		if (postojiPut(x - 1, y)) {
+			return true;
+		}
+		if (postojiPut(x, y + 1)) {
+			return true;
+		}
+		if (postojiPut(x, y - 1)) {
+			return true;
+		}
+		m.setPos(x, y, false);
+		return false;
+	}
+
+	// Poziva metodu rput da pronadje i ispise put, ako postoji
+	// Ukoliko put ne postoji, ispisuje poruku o gresci
+	public void nadjiPut(int x, int y) {
+		if (!rput(x, y)) {
+			System.err.println("Ne postoji put");
+		}
+	}
+
+	// Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
+	// Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom
+	// redosledu
+	// Put se stampa pri povratku iz rekurzije
+	private boolean rput(int x, int y) {
+		if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
+			return false;
+		}
+		if (m.getPos(x, y)) {
+			return false;
+		}
+		if (m.getMat(x, y) == Mapa.ZID) {
+			return false;
+		}
+		if (m.getMat(x, y) == Mapa.IZLAZ) {
+			System.out.println(x + " " + y);
+			return true;
+		}
+		m.setPos(x, y, true);
+		if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)
+				|| rput(x - 1, y)) {
+			System.out.println(x + " " + y);
+			return true;
+		}
+		m.setPos(x, y, false);
+		return false;
+	}
+
+	// Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
+	// koristi komparator po duzini resenja, tj. trazi se najkrace resenje
+	// Samo resenje kreira se u metodi optPut
+	public Put najkraciPut(int x, int y) {
+		Put r = new Put();
+		optPut(x, y, r, new KomparatorPoDuzini());
+		return optResenje;
+	}
+
+	// Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
+	// koristi komparator po duzini resenja, tj. trazi se najvrednije resenje
+	// Samo resenje kreira se u metodi optPut
+	public Put najvrednijiPut(int x, int y) {
+		Put trenutni = new Put();
+		optPut(x, y, trenutni, new KomparatorPoVredosti());
+		return optResenje;
+	}
+
+	// Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
+	// Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u
+	// optResenje
+	// Optimalnost puta se proverava komparatorom
+	private void optPut(int x, int y, Put trenutni, Comparator<Put> c) {
+		if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {
+			return;
+		}
+		if (m.getPos(x, y)) {
+			return;
+		}
+		if (m.getMat(x, y) == Mapa.ZID) {
+			return;
+		}
+		if (m.getMat(x, y) == Mapa.IZLAZ) {
+			trenutni.dodaj(x, y, 0);
+			if (optResenje == null || c.compare(trenutni, optResenje) < 0) {
+				optResenje = new Put(trenutni);
+			}
+			trenutni.izbaciKraj();
+			return;
+		}
+
+		// pokusavamo da trazimo dalje put
+		m.setPos(x, y, true);
+		trenutni.dodaj(x, y, m.getMat(x, y));
+		optPut(x + 1, y, trenutni, c);
+		optPut(x, y + 1, trenutni, c);
+		optPut(x, y - 1, trenutni, c);
+		optPut(x - 1, y, trenutni, c);
+		m.setPos(x, y, false);
+		trenutni.izbaciKraj();
+	}
+}
+
+// Komparator za puteve  po duzini resenja
+class KomparatorPoDuzini implements Comparator<Put> {
+	public int compare(Put r1, Put r2) {
+		return r1.getLength() - r2.getLength();
+	}
+}
+
+// Komparator za puteve po vrednosti resenja
+class KomparatorPoVredosti implements Comparator<Put> {
+	public int compare(Put r1, Put r2) {
+		return r2.getVrednost() - r1.getVrednost();
+	}
+}