PretrazivanjeSaVracanjem/Lavirint/PostojanjePuta/PostojanjePuta.java

   1 public class PostojanjePuta {
   2
   3         // konstante za bolju citljivost i lakse prepravljanje
   4         public final static int IZLAZ = -99;
   5         public final static int ZID = -11;
   6
   7         // dimenzije matrice koja je mapa
   8         private static int visina, sirina;
   9         // matrica sa mapom
  10         private static int[][] mat;
  11         // mastrica posecenosti polja
  12         private static boolean[][] pos;
  13
  14         /* ucitava podatke iz fajla i vraca da li je
  15                 uspesno ucitano */
  16         private static boolean ucitaj(String imeFajla) {
  17                 if (!Svetovid.testIn(imeFajla)) {
  18                         return false;
  19                 }
  20
  21                 sirina = Svetovid.in(imeFajla).readInt();
  22                 visina = Svetovid.in(imeFajla).readInt();
  23                 if (sirina >= 0 && visina >= 0) {
  24                         mat = new int[sirina][visina];
  25                         pos = new boolean[sirina][visina];
  26                         for (int j = 0; j < visina; j++) {
  27                                 for (int i = 0; i < sirina; i++) {
  28                                         mat[i][j] = Svetovid.in(imeFajla).readInt();
  29                                 }
  30                         }
  31                         Svetovid.closeIn(imeFajla);
  32                         return true;
  33                 } else {
  34                         Svetovid.closeIn(imeFajla);
  35                         return false;
  36                 }
  37
  38         }
  39
  40         private static void stampaj() {
  41                 if (visina != 0 && sirina != 0) {
  42                         System.out.println(visina + " " + sirina);
  43                         for (int j = 0; j < visina; j++) {
  44                                 for (int i = 0; i < sirina; i++) {
  45                                         // za uredno stampanje koristimo printf
  46                                         // ali mozemo i "normalno" stampanje koristiti
  47                                         System.out.printf("%1$5d", mat[i][j]);
  48                                 }
  49                                 System.out.println();
  50                         }
  51                 }
  52         }
  53
  54         // Provarava da li postoji put do izlaza i vraca vrednost true
  55         // ako postoji put ili vrednost false ako ne postoji
  56         private static boolean postojiPut(int x, int y) {
  57                 // prvo provervamo jesmo li "u matrici"
  58                 if (x < 0 || x >= sirina || y < 0 || y >= visina) {
  59                         return false;
  60                 }
  61
  62                 // da li smo vec bili ovde?
  63                 if (pos[x][y]) {
  64                         return false;
  65                 }
  66                 // da li je ovo zid?
  67                 if (mat[x][y] == ZID) {
  68                         return false;
  69                 }
  70                 if (mat[x][y] == IZLAZ) {
  71                         return true;
  72                 }
  73
  74                 // postavljamo da smo bili ovde
  75                 pos[x][y] = true;
  76
  77                 // pitamo susede da li oni znaju put?
  78                 if (postojiPut(x + 1, y)) {
  79                         return true;
  80                 }
  81                 if (postojiPut(x - 1, y)) {
  82                         return true;
  83                 }
  84                 if (postojiPut(x, y + 1)) {
  85                         return true;
  86                 }
  87
  88                 if (postojiPut(x, y - 1)) {
  89                         return true;
  90                 }
  91
  92                 pos[x][y] = false;
  93
  94                 // nismo uspeli da nadjemo put
  95                 // znaci da ga nema
  96                 return false;
  97         }
  98
  99         public static void main(String[] args) {
 100                 System.out.println("unesite ime fajla:");
 101                 String imef = Svetovid.in.readLine();
 102
 103                 // za lakse testiranje predpostavimo neki fajl
 104                 // ako nista nije uneto
 105                 if (imef.equals(""))
 106                         imef = "lav1.txt";
 107
 108                 if (ucitaj(imef)) {
 109                         stampaj();
 110                         System.out.println(postojiPut(0,0));
 111                 } else {
 112                         System.out.println("greska u citanju fajla!");
 113                 }
 114         }
 115 }