gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / SuperKomplikovanoResenje / Lavirint.java
diff --git a/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/SuperKomplikovanoResenje/Lavirint.java
*/\r
public class Lavirint {\r
\r
- // Polje m sadrzi kompletnu mapu\r
- private Mapa m;\r
+ // Polje m sadrzi kompletnu mapu\r
+ private Mapa m;\r
\r
- // Polje optResenje sluzi za pamcenje optimalnog resenja\r
- private Put optResenje;\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
- public Lavirint(String imeFajla) {\r
- m = new Mapa(imeFajla);\r
- m.stampaj();\r
- }\r
+ // Ucitava mapu iz datog fajla i stampa je na ekran\r
+ public Lavirint(String imeFajla) {\r
+ m = new Mapa(imeFajla);\r
+ m.stampaj();\r
+ }\r
\r
- // Provarava da li postoji put do izlaza i vraca vrednost true\r
- // ako postoji put ili vrednost false ako ne postoji\r
- public boolean postojiPut(int x, int y) {\r
- if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
- return false;\r
- }\r
- if (m.getPos(x, y) == true) {\r
- return false;\r
- }\r
- if (m.getMat(x, y) == Mapa.ZID) {\r
- return false;\r
- }\r
- if (m.getMat(x, y) == Mapa.IZLAZ) {\r
- return true;\r
- }\r
- m.setPos(x, y, true);\r
- if (postojiPut(x + 1, y)) {\r
- return true;\r
- }\r
- if (postojiPut(x - 1, y)) {\r
- return true;\r
- }\r
- if (postojiPut(x, y + 1)) {\r
- return true;\r
- }\r
- if (postojiPut(x, y - 1)) {\r
- return true;\r
- }\r
- m.setPos(x, y, false);\r
- return false;\r
- }\r
+ // Provarava da li postoji put do izlaza i vraca vrednost true\r
+ // ako postoji put ili vrednost false ako ne postoji\r
+ public boolean postojiPut(int x, int y) {\r
+ if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
+ return false;\r
+ }\r
+ if (m.getPos(x, y) == true) {\r
+ return false;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.ZID) {\r
+ return false;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.IZLAZ) {\r
+ return true;\r
+ }\r
+ m.setPos(x, y, true);\r
+ if (postojiPut(x + 1, y)) {\r
+ return true;\r
+ }\r
+ if (postojiPut(x - 1, y)) {\r
+ return true;\r
+ }\r
+ if (postojiPut(x, y + 1)) {\r
+ return true;\r
+ }\r
+ if (postojiPut(x, y - 1)) {\r
+ return true;\r
+ }\r
+ m.setPos(x, y, false);\r
+ return false;\r
+ }\r
\r
- // Poziva metodu rput da pronadje i ispise put, ako postoji\r
- // Ukoliko put ne postoji, ispisuje poruku o gresci\r
- public void nadjiPut(int x, int y) {\r
- if (!rput(x, y)) {\r
- System.err.println("Ne postoji put");\r
- }\r
- }\r
+ // Poziva metodu rput da pronadje i ispise put, ako postoji\r
+ // Ukoliko put ne postoji, ispisuje poruku o gresci\r
+ public void nadjiPut(int x, int y) {\r
+ if (!rput(x, y)) {\r
+ System.err.println("Ne postoji put");\r
+ }\r
+ }\r
\r
- // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
- // Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom\r
- // redosledu\r
- // Put se stampa pri povratku iz rekurzije\r
- private boolean rput(int x, int y) {\r
- if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
- return false;\r
- }\r
- if (m.getPos(x, y)) {\r
- return false;\r
- }\r
- if (m.getMat(x, y) == Mapa.ZID) {\r
- return false;\r
- }\r
- if (m.getMat(x, y) == Mapa.IZLAZ) {\r
- System.out.println(x + " " + y);\r
- return true;\r
- }\r
- m.setPos(x, y, true);\r
- if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)\r
- || rput(x - 1, y)) {\r
- System.out.println(x + " " + y);\r
- return true;\r
- }\r
- m.setPos(x, y, false);\r
- return false;\r
- }\r
+ // Proverava da li postoji put korsiteci pretrazivanje sa vracanjem\r
+ // Ukoliko se pronadje izlaz iz lavirinta, stampa se put u obrnutom\r
+ // redosledu\r
+ // Put se stampa pri povratku iz rekurzije\r
+ private boolean rput(int x, int y) {\r
+ if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
+ return false;\r
+ }\r
+ if (m.getPos(x, y)) {\r
+ return false;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.ZID) {\r
+ return false;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.IZLAZ) {\r
+ System.out.println(x + " " + y);\r
+ return true;\r
+ }\r
+ m.setPos(x, y, true);\r
+ if (rput(x + 1, y) || rput(x, y + 1) || rput(x, y - 1)\r
+ || rput(x - 1, y)) {\r
+ System.out.println(x + " " + y);\r
+ return true;\r
+ }\r
+ m.setPos(x, y, false);\r
+ return false;\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
+ // 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 trenutni = new Put();\r
- optPut(x, y, trenutni, new KomparatorPoVredosti());\r
- return optResenje;\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 trenutni = new Put();\r
+ optPut(x, y, trenutni, 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 puta se proverava komparatorom\r
- private void optPut(int x, int y, Put trenutni, Comparator<Put> c) {\r
- if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
- return;\r
- }\r
- if (m.getPos(x, y)) {\r
- return;\r
- }\r
- if (m.getMat(x, y) == Mapa.ZID) {\r
- return;\r
- }\r
- if (m.getMat(x, y) == Mapa.IZLAZ) {\r
- trenutni.dodaj(x, y, 0);\r
- if (optResenje == null || c.compare(trenutni, optResenje) < 0) {\r
- optResenje = new Put(trenutni);\r
- }\r
- trenutni.izbaciKraj();\r
- return;\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 puta se proverava komparatorom\r
+ private void optPut(int x, int y, Put trenutni, Comparator<Put> c) {\r
+ if (x < 0 || x >= m.getSirina() || y < 0 || y >= m.getVisina()) {\r
+ return;\r
+ }\r
+ if (m.getPos(x, y)) {\r
+ return;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.ZID) {\r
+ return;\r
+ }\r
+ if (m.getMat(x, y) == Mapa.IZLAZ) {\r
+ trenutni.dodaj(x, y, 0);\r
+ if (optResenje == null || c.compare(trenutni, optResenje) < 0) {\r
+ optResenje = new Put(trenutni);\r
+ }\r
+ trenutni.izbaciKraj();\r
+ return;\r
+ }\r
\r
- // pokusavamo da trazimo dalje put\r
- m.setPos(x, y, true);\r
- trenutni.dodaj(x, y, m.getMat(x, y));\r
- optPut(x + 1, y, trenutni, c);\r
- optPut(x, y + 1, trenutni, c);\r
- optPut(x, y - 1, trenutni, c);\r
- optPut(x - 1, y, trenutni, c);\r
- m.setPos(x, y, false);\r
- trenutni.izbaciKraj();\r
- }\r
+ // pokusavamo da trazimo dalje put\r
+ m.setPos(x, y, true);\r
+ trenutni.dodaj(x, y, m.getMat(x, y));\r
+ optPut(x + 1, y, trenutni, c);\r
+ optPut(x, y + 1, trenutni, c);\r
+ optPut(x, y - 1, trenutni, c);\r
+ optPut(x - 1, y, trenutni, c);\r
+ m.setPos(x, y, false);\r
+ trenutni.izbaciKraj();\r
+ }\r
}\r
\r
// Komparator za puteve 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
+ public int compare(Put r1, Put r2) {\r
+ return r1.getLength() - r2.getLength();\r
+ }\r
}\r
\r
// Komparator za puteve 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
+ public int compare(Put r1, Put r2) {\r
+ return r2.getVrednost() - r1.getVrednost();\r
+ }\r
}\r