gitweb on Svarog

projekti pod git sistemom za održavanje verzija -- projects under the git version control system
Hash, doterivanje tekstualnog materijala
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / NajboljiPut / NajboljiPut.java
2 /**
3 * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva.
4 *
5 * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore
6 * koji se korste pri trazenju najkraceg i najvrednijeg puta.
7 */
9 import java.util.Comparator;
11 public class NajboljiPut {
13 // Konstante za polja u mapi
14 public final static int IZLAZ = -99;
15 public final static int ZID = -11;
17 // interno predstavljanje mape
18 private int visina, sirina;
19 private int[][] mat;
20 // matrica posecenih polja
21 private boolean[][] pos;
23 // Polje optResenje sluzi za pamcenje optimalnog resenja
24 private Put optResenje;
26 // Ucitava mapu iz datog fajla i stampa je na ekran
27 NajboljiPut(String imeFajla) {
28 if (!Svetovid.testIn(imeFajla)) {
29 throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan");
30 }
32 sirina = Svetovid.in(imeFajla).readInt();
33 visina = Svetovid.in(imeFajla).readInt();
34 mat = new int[sirina][visina];
35 pos = new boolean[sirina][visina];
36 for (int j = 0; j < visina; j++) {
37 for (int i = 0; i < sirina; i++) {
38 mat[i][j] = Svetovid.in(imeFajla).readInt();
39 }
40 }
41 Svetovid.closeIn(imeFajla);
43 stampajMapu();
44 }
46 private void stampajMapu() {
47 if (visina > 0 && sirina > 0) {
48 System.out.println(visina + " " + sirina);
49 for (int j = 0; j < visina; j++) {
50 for (int i = 0; i < sirina; i++) {
51 System.out.print(mat[i][j] + "\t");
52 }
53 System.out.println();
54 }
55 }
56 }
58 // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
59 // koristi komparator po duzini resenja, tj. trazi se najkrace resenje
60 // Samo resenje kreira se u metodi optPut
61 public Put najkraciPut(int x, int y) {
62 Put r = new Put();
63 optPut(x, y, r, new KomparatorPoDuzini());
64 return optResenje;
65 }
67 // Kreira optimalno resenje za put, pri cemu se za optimalnost resenja
68 // koristi komparator po duzini resenja, tj. trazi se najvrednije resenje
69 // Samo resenje kreira se u metodi optPut
70 public Put najvrednijiPut(int x, int y) {
71 Put r = new Put();
72 optPut(x, y, r, new KomparatorPoVredosti());
73 return optResenje;
74 }
76 // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem
77 // Ukoliko se pronadje na prvi ili optimalniji put, taj put se pamti u
78 // optResenje
79 // Optimalnost resenja se proverava komparatorom
80 private void optPut(int x, int y, Put r, Comparator<Put> c) {
81 if (x < 0 || x >= sirina || y < 0 || y >= visina) {
82 return;
83 }
84 if (pos[x][y]) {
85 return;
86 }
87 if (mat[x][y] == ZID) {
88 return;
89 }
90 if (mat[x][y] == IZLAZ) {
91 r.dodaj(x, y, 0);
92 if (optResenje == null || c.compare(r, optResenje) < 0) {
93 optResenje = r.kopija();
94 }
95 r.izbaciKraj();
96 return;
97 }
99 // pokusavamo da trazimo dalje put
100 pos[x][y] = true;
101 r.dodaj(x, y, mat[x][y]);
102 optPut(x + 1, y, r, c);
103 optPut(x, y + 1, r, c);
104 optPut(x, y - 1, r, c);
105 optPut(x - 1, y, r, c);
106 pos[x][y] = false;
107 r.izbaciKraj();
110 public static void main(String[] args) {
111 Svetovid.out.println("Unesite ime fajla: ");
112 String fajl = Svetovid.in.readLine();
113 if (!Svetovid.testIn(fajl)) {
114 System.out.println("Greska: nema fajla!");
115 return;
118 NajboljiPut l = new NajboljiPut(fajl);
119 Put r;
121 System.out.println("Unesite koordinate za pocetak:");
122 System.out.println("x?");
123 int x = Svetovid.in.readInt();
124 System.out.println("y?");
125 int y = Svetovid.in.readInt();
127 System.out.println("Najkraci put je:");
128 r = l.najkraciPut(x, y);
129 if (r != null) {
130 r.stampaj();
131 } else {
132 System.out.println("Nema resenja");
135 System.out.println("Najvredniji put je:");
136 r = l.najvrednijiPut(0, 0);
137 if (r != null) {
138 r.stampaj();
139 System.out.println("Vrednost puta: " + r.getVrednost());
140 } else {
141 System.out.println("Nema resenja");
146 // Komparator za resenja po duzini resenja
147 class KomparatorPoDuzini implements Comparator<Put> {
148 public int compare(Put r1, Put r2) {
149 return r1.getLength() - r2.getLength();
153 // Komparator za resenja po vrednosti resenja
154 class KomparatorPoVredosti implements Comparator<Put> {
155 public int compare(Put r1, Put r2) {
156 return r2.getVrednost() - r1.getVrednost();
Svarog.pmf.uns.ac.rs/gitweb maintanance Doni Pracner