X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=blobdiff_plain;f=PretrazivanjeSaVracanjem%2FLavirint%2FNajboljiPut%2FNajboljiPut.java;h=b178b78534792ef8a26d6a85cf2da512503c48be;hp=f0756b0f86a6b79c30a397306de75ed0b4ab7b2e;hb=259cc384743122b180e79a962ec0f11634a5b67c;hpb=2f2710782e8107fc8dd587e6b70212e521561c42

diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
index f0756b0..b178b78 100644
--- a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
+++ b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
@@ -1,12 +1,112 @@
+
 /**
- * Program za nalazenje puta u lavirintu.
+ * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva.
  * 
- * Date su dva varijante problema optimalnog puta, najkraci
- * put i najvredniji put.
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.
  */
 
+import java.util.Comparator;
+
 public class NajboljiPut {
 
+	// Konstante za polja u mapi
+	public final static int IZLAZ = -99;
+	public final static int ZID = -11;
+
+	// interno predstavljanje mape
+	private int visina, sirina;
+	private int[][] mat;
+	// matrica posecenih polja
+	private boolean[][] pos;
+
+	// Polje optResenje sluzi za pamcenje optimalnog resenja
+	private Put optResenje;
+
+	// Ucitava mapu iz datog fajla i stampa je na ekran
+	NajboljiPut(String imeFajla) {
+		if (!Svetovid.testIn(imeFajla)) {
+			throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan");
+		}
+
+		sirina = Svetovid.in(imeFajla).readInt();
+		visina = Svetovid.in(imeFajla).readInt();
+		mat = new int[sirina][visina];
+		pos = new boolean[sirina][visina];
+		for (int j = 0; j < visina; j++) {
+			for (int i = 0; i < sirina; i++) {
+				mat[i][j] = Svetovid.in(imeFajla).readInt();
+			}
+		}
+		Svetovid.closeIn(imeFajla);
+
+		stampajMapu();
+	}
+
+	private void stampajMapu() {
+		if (visina > 0 && sirina > 0) {
+			System.out.println(visina + " " + sirina);
+			for (int j = 0; j < visina; j++) {
+				for (int i = 0; i < sirina; i++) {
+					System.out.print(mat[i][j] + "\t");
+				}
+				System.out.println();
+			}
+		}
+	}
+
+	// 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 r = new Put();
+		optPut(x, y, r, 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 resenja se proverava komparatorom
+	private void optPut(int x, int y, Put r, Comparator<Put> c) {
+		if (x < 0 || x >= sirina || y < 0 || y >= visina) {
+			return;
+		}
+		if (pos[x][y]) {
+			return;
+		}
+		if (mat[x][y] == ZID) {
+			return;
+		}
+		if (mat[x][y] == IZLAZ) {
+			r.dodaj(x, y, 0);
+			if (optResenje == null || c.compare(r, optResenje) < 0) {
+				optResenje = r.kopija();
+			}
+			r.izbaciKraj();
+			return;
+		}
+
+		// pokusavamo da trazimo dalje put
+		pos[x][y] = true;
+		r.dodaj(x, y, mat[x][y]);
+		optPut(x + 1, y, r, c);
+		optPut(x, y + 1, r, c);
+		optPut(x, y - 1, r, c);
+		optPut(x - 1, y, r, c);
+		pos[x][y] = false;
+		r.izbaciKraj();
+	}
+
 	public static void main(String[] args) {
 		Svetovid.out.println("Unesite ime fajla: ");
 		String fajl = Svetovid.in.readLine();
@@ -15,8 +115,8 @@ public class NajboljiPut {
 			return;
 		}
 
-		Lavirint l = new Lavirint(fajl);
-		Resenje r;
+		NajboljiPut l = new NajboljiPut(fajl);
+		Put r;
 
 		System.out.println("Unesite koordinate za pocetak:");
 		System.out.println("x?");
@@ -41,4 +141,18 @@ public class NajboljiPut {
 			System.out.println("Nema resenja");
 		}
 	}
+}
+
+// Komparator za resenja po duzini resenja
+class KomparatorPoDuzini implements Comparator<Put> {
+	public int compare(Put r1, Put r2) {
+		return r1.getLength() - r2.getLength();
+	}
+}
+
+// Komparator za resenja po vrednosti resenja
+class KomparatorPoVredosti implements Comparator<Put> {
+	public int compare(Put r1, Put r2) {
+		return r2.getVrednost() - r1.getVrednost();
+	}
 }
\ No newline at end of file