Zadatak nalazenje da li postoji put u lavirintu.

[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / PostojanjePuta / Lavirint.java

diff --git a/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/Lavirint.java
new file mode 100644 (file)
index 0000000..3dd580f
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/Lavirint.java
@@ -0,0 +1,86 @@
+/**\r
+ * Klasa Lavirint sadrzi 2 javne i jednu privatnu metodu za trazenje puteva.\r
+ * \r
+ */\r
+\r
+public class Lavirint {\r
+\r
+ // Polje m sadrzi kompletnu mapu\r
+ private Mapa m;\r
+\r
+ // Ucitava mapu iz datog fajla i stampa je na ekran\r
+ Lavirint(String imeFajla) {\r
+  m = Mapa.ucitajIzFajla(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
+  } else {\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
+\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
+  } else {\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
+}\r