gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java b/PretrazivanjeSaVracanjem/Lavirint/NajboljiPut/NajboljiPut.java
+\r
/**\r
- * Program za nalazenje puta u lavirintu.\r
+ * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva.\r
* \r
- * Date su dva varijante problema optimalnog puta, najkraci\r
- * put i najvredniji put.\r
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore\r
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.\r
*/\r
\r
+import java.util.Comparator;\r
+\r
public class NajboljiPut {\r
\r
+ // Konstante za polja u mapi\r
+ public final static int IZLAZ = -99;\r
+ public final static int ZID = -11;\r
+\r
+ // interno predstavljanje mape\r
+ private int visina, sirina;\r
+ private int[][] mat;\r
+ // matrica posecenih polja\r
+ private boolean[][] pos;\r
+\r
+ // Polje optResenje sluzi za pamcenje optimalnog resenja\r
+ private Put optResenje;\r
+\r
+ // Ucitava mapu iz datog fajla i stampa je na ekran\r
+ NajboljiPut(String imeFajla) {\r
+ if (!Svetovid.testIn(imeFajla)) {\r
+ throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan");\r
+ }\r
+\r
+ sirina = Svetovid.in(imeFajla).readInt();\r
+ visina = Svetovid.in(imeFajla).readInt();\r
+ mat = new int[sirina][visina];\r
+ pos = new boolean[sirina][visina];\r
+ for (int j = 0; j < visina; j++) {\r
+ for (int i = 0; i < sirina; i++) {\r
+ mat[i][j] = Svetovid.in(imeFajla).readInt();\r
+ }\r
+ }\r
+ Svetovid.closeIn(imeFajla);\r
+\r
+ stampajMapu();\r
+ }\r
+\r
+ private void stampajMapu() {\r
+ if (visina > 0 && sirina > 0) {\r
+ System.out.println(visina + " " + sirina);\r
+ for (int j = 0; j < visina; j++) {\r
+ for (int i = 0; i < sirina; i++) {\r
+ System.out.print(mat[i][j] + "\t");\r
+ }\r
+ System.out.println();\r
+ }\r
+ }\r
+ }\r
+\r
+ // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+ // koristi komparator po duzini resenja, tj. trazi se najkrace resenje\r
+ // Samo resenje kreira se u metodi optPut\r
+ public Put najkraciPut(int x, int y) {\r
+ Put r = new Put();\r
+ optPut(x, y, r, new KomparatorPoDuzini());\r
+ return optResenje;\r
+ }\r
+\r
+ // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja\r
+ // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje\r
+ // Samo resenje kreira se u metodi optPut\r
+ public Put najvrednijiPut(int x, int y) {\r
+ Put r = new Put();\r
+ optPut(x, y, r, new KomparatorPoVredosti());\r
+ return optResenje;\r
+ }\r
+\r
+ // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
+ // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u\r
+ // optResenje\r
+ // Optimalnost resenja se proverava komparatorom\r
+ private void optPut(int x, int y, Put r, Comparator<Put> c) {\r
+ if (x < 0 || x >= sirina || y < 0 || y >= visina) {\r
+ return;\r
+ }\r
+ if (pos[x][y]) {\r
+ return;\r
+ }\r
+ if (mat[x][y] == ZID) {\r
+ return;\r
+ }\r
+ if (mat[x][y] == IZLAZ) {\r
+ r.dodaj(x, y, 0);\r
+ if (optResenje == null || c.compare(r, optResenje) < 0) {\r
+ optResenje = r.kopija();\r
+ }\r
+ r.izbaciKraj();\r
+ return;\r
+ }\r
+\r
+ // pokusavamo da trazimo dalje put\r
+ pos[x][y] = true;\r
+ r.dodaj(x, y, mat[x][y]);\r
+ optPut(x + 1, y, r, c);\r
+ optPut(x, y + 1, r, c);\r
+ optPut(x, y - 1, r, c);\r
+ optPut(x - 1, y, r, c);\r
+ pos[x][y] = false;\r
+ r.izbaciKraj();\r
+ }\r
+\r
public static void main(String[] args) {\r
Svetovid.out.println("Unesite ime fajla: ");\r
String fajl = Svetovid.in.readLine();\r
return;\r
}\r
\r
- Lavirint l = new Lavirint(fajl);\r
- Resenje r;\r
+ NajboljiPut l = new NajboljiPut(fajl);\r
+ Put r;\r
\r
System.out.println("Unesite koordinate za pocetak:");\r
System.out.println("x?");\r
System.out.println("Nema resenja");\r
}\r
}\r
+}\r
+\r
+// Komparator za resenja po duzini resenja\r
+class KomparatorPoDuzini implements Comparator<Put> {\r
+ public int compare(Put r1, Put r2) {\r
+ return r1.getLength() - r2.getLength();\r
+ }\r
+}\r
+\r
+// Komparator za resenja po vrednosti resenja\r
+class KomparatorPoVredosti implements Comparator<Put> {\r
+ public int compare(Put r1, Put r2) {\r
+ return r2.getVrednost() - r1.getVrednost();\r
+ }\r
}
\ No newline at end of file