PostojanjePuta, jednostavno resenje

diff --git a/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/PostojanjePuta.java b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/PostojanjePuta.java
new file mode 100644 (file)
index 0000000..834be7e
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/PostojanjePuta.java
@@ -0,0 +1,115 @@
+public class PostojanjePuta {
+
+       // konstante za bolju citljivost i lakse prepravljanje
+       public final static int IZLAZ = -99;
+       public final static int ZID = -11;
+       
+       // dimenzije matrice koja je mapa
+       private static int visina, sirina;
+       // matrica sa mapom
+       private static int[][] mat;
+       // mastrica posecenosti polja
+       private static boolean[][] pos;
+       
+       /* ucitava podatke iz fajla i vraca da li je
+               uspesno ucitano */
+       private static boolean ucitaj(String imeFajla) {
+               if (!Svetovid.testIn(imeFajla)) {
+                       return false;
+               }
+               
+               sirina = Svetovid.in(imeFajla).readInt();
+               visina = Svetovid.in(imeFajla).readInt();
+               if (sirina >= 0 && visina >= 0) {
+                       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);
+                       return true;
+               } else {
+                       Svetovid.closeIn(imeFajla);
+                       return false;
+               }
+               
+       }
+
+       private static void stampaj() {
+               if (visina != 0 && sirina != 0) {
+                       System.out.println(visina + " " + sirina);
+                       for (int j = 0; j < visina; j++) {
+                               for (int i = 0; i < sirina; i++) {
+                                       // za uredno stampanje koristimo printf
+                                       // ali mozemo i "normalno" stampanje koristiti
+                                       System.out.printf("%1$5d", mat[i][j]);
+                               }
+                               System.out.println();
+                       }
+               }
+       }
+
+       // Provarava da li postoji put do izlaza i vraca vrednost true
+       // ako postoji put ili vrednost false ako ne postoji
+       private static boolean postojiPut(int x, int y) {
+               // prvo provervamo jesmo li "u matrici"
+               if (x < 0 || x >= sirina || y < 0 || y >= visina) {
+                       return false;
+               }
+               
+               // da li smo vec bili ovde?
+               if (pos[x][y]) {
+                       return false;
+               }
+               // da li je ovo zid?
+               if (mat[x][y] == ZID) {
+                       return false;
+               }
+               if (mat[x][y] == IZLAZ) {
+                       return true;
+               }
+               
+               // postavljamo da smo bili ovde
+               pos[x][y] = true;
+               
+               // pitamo susede da li oni znaju put?
+               if (postojiPut(x + 1, y)) {
+                       return true;
+               }
+               if (postojiPut(x - 1, y)) {
+                       return true;
+               }
+               if (postojiPut(x, y + 1)) {
+                       return true;
+               }
+               
+               if (postojiPut(x, y - 1)) {
+                       return true;
+               }
+               
+               pos[x][y] = false;
+               
+               // nismo uspeli da nadjemo put
+               // znaci da ga nema
+               return false;           
+       }
+       
+       public static void main(String[] args) {
+               System.out.println("unesite ime fajla:");
+               String imef = Svetovid.in.readLine();
+               
+               // za lakse testiranje predpostavimo neki fajl
+               // ako nista nije uneto
+               if (imef.equals("")) 
+                       imef = "lav1.txt";
+               
+               if (ucitaj(imef)) {
+                       stampaj();
+                       System.out.println(postojiPut(0,0));
+               } else {
+                       System.out.println("greska u citanju fajla!");
+               }
+       }
+}
\ No newline at end of file