gitweb on Svarog

projekti pod git sistemom za održavanje verzija -- projects under the git version control system
Lavirint, primer pretrazivanja sa vracanjem za test
authorSasa Tosic <sashat@dmi.uns.ac.rs>
Sat, 7 Nov 2015 20:58:15 +0000 (21:58 +0100)
committerDoni Pracner <quinnuendo@gmail.com>
Sat, 7 Nov 2015 20:58:15 +0000 (21:58 +0100)
17 files changed:
PretrazivanjeSaVracanjem/Lavirint/Lavirint.java [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/LavirintProgram.java [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/Mapa.java [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/Polje.java [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/Resenje.java [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/blago1.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/blago2.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/blago3.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/l-prazan.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/l1.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/l2.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/l3.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/l4.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/lav.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/lavblok.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/readme.txt [new file with mode: 0644]
PretrazivanjeSaVracanjem/Lavirint/zadatak-lavirint.txt [new file with mode: 0644]

diff --git a/PretrazivanjeSaVracanjem/Lavirint/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/Lavirint.java
new file mode 100644 (file)
index 0000000..4fd8f79
--- /dev/null
@@ -0,0 +1,156 @@
+/**\r
+ * Klasa Lavirint sadrzi 3 javne i tri privatne metode za trazenje puteva.\r
+ * \r
+ * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore\r
+ * koji se korste pri trazenju najkraceg i najvrednijeg puta.\r
+ */\r
+\r
+import java.util.Comparator;\r
+\r
+public class Lavirint {\r
+\r
+       // Polje m sadrzi kompletnu mapu\r
+       private Mapa m;\r
+       // Polje optResenje sluzi za pamcenje optimalnog resenja\r
+       private Resenje optResenje;\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
+       // 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 Resenje najkraciPut(int x, int y) {\r
+               Resenje r = new Resenje();\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 Resenje najvrednijiPut(int x, int y) {\r
+               Resenje r = new Resenje();\r
+               optPut(x, y, r, 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 resenja se proverava komparatorom\r
+       private void optPut(int x, int y, Resenje r, Comparator<Resenje> 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
+                       r.dodaj(x, y, 0);\r
+                       if (optResenje == null || c.compare(r, optResenje) < 0) {\r
+                               optResenje = r.clone();\r
+                       }\r
+                       r.izbaciKraj();\r
+               } else {\r
+                       m.setPos(x, y, true);\r
+                       r.dodaj(x, y, m.getMat(x, y));\r
+                       optPut(x + 1, y, r, c);\r
+                       optPut(x, y + 1, r, c);\r
+                       optPut(x, y - 1, r, c);\r
+                       optPut(x - 1, y, r, c);\r
+                       m.setPos(x, y, false);\r
+                       r.izbaciKraj();\r
+               }\r
+       }\r
+}\r
+\r
+// Komparator za resenja po duzini resenja\r
+class KomparatorPoDuzini implements Comparator<Resenje> {\r
+       public int compare(Resenje r1, Resenje r2) {\r
+               return r1.getLength() - r2.getLength();\r
+       }\r
+}\r
+\r
+// Komparator za resenja po vrednosti resenja\r
+class KomparatorPoVredosti implements Comparator<Resenje> {\r
+       public int compare(Resenje r1, Resenje r2) {\r
+               return r2.getVrednost() - r1.getVrednost();\r
+       }\r
+}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/LavirintProgram.java b/PretrazivanjeSaVracanjem/Lavirint/LavirintProgram.java
new file mode 100644 (file)
index 0000000..6566938
--- /dev/null
@@ -0,0 +1,71 @@
+/**\r
+ * Program za nalazenje puta u lavirintu.\r
+ * \r
+ * Date su cetiri varijante problema, od jednostavnijih ka slozenijima, radi\r
+ * ilustracije osnovnih koncepata i postepenog uvodjenja novih.\r
+ * \r
+ * Najjednostavnije je samo nalazenje da li put postoji.\r
+ * \r
+ * Prosirenje tog resenja nam ispisuje taj nadjeni put.\r
+ * \r
+ * Treca varijanta nalazi sve puteve i medju njima bira najkraci.\r
+ * \r
+ * Cetvrta varijanta resava lavirint u kome su rasuti zlatnici na poljima i\r
+ * nalazi put na kome se kupi najvise zlatnika.\r
+ */\r
+\r
+public class LavirintProgram {\r
+\r
+       public static void main(String[] args) {\r
+               Svetovid.out.println("Unesite ime fajla: ");\r
+               String fajl = Svetovid.in.readLine();\r
+               if (!Svetovid.testIn(fajl)) {\r
+                       System.out.println("Greska: nema fajla!");\r
+                       return;\r
+               }\r
+\r
+               Lavirint l = new Lavirint(fajl);\r
+               Resenje r;\r
+\r
+               if (l != null) {\r
+                       System.out.println("1 - da li postoji put");\r
+                       System.out.println("2 - ispis nekog puta (ako postoji)");\r
+                       System.out.println("3 - nalazenje najkraceg puta");\r
+                       System.out.println("4 - nalazenje najvrednijeg puta");\r
+                       System.out.println("Unesite izbor 1-4:");\r
+                       int op = Svetovid.in.readInt();\r
+\r
+                       switch (op) {\r
+                       case 1:\r
+                               if (l.postojiPut(0, 0)) {\r
+                                       System.out.println("Postoji put");\r
+                               } else {\r
+                                       System.out.println("Ne postoji put");\r
+                               }\r
+                               break;\r
+                       case 2:\r
+                               l.nadjiPut(0, 0);\r
+                               break;\r
+                       case 3:\r
+                               r = l.najkraciPut(0, 0);\r
+                               if (r != null) {\r
+                                       r.stampaj();\r
+                               } else {\r
+                                       System.out.println("Nema resenja");\r
+                               }\r
+                               break;\r
+                       case 4:\r
+                               r = l.najvrednijiPut(0, 0);\r
+                               if (r != null) {\r
+                                       r.stampaj();\r
+                                       System.out.println("Vrednost puta: " + r.getVrednost());\r
+                               } else {\r
+                                       System.out.println("Nema resenja");\r
+                               }\r
+                               break;\r
+                       default:\r
+                               System.err.println("Uneli ste pogresan izbor");\r
+                       }\r
+               }\r
+       }\r
+}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/Mapa.java b/PretrazivanjeSaVracanjem/Lavirint/Mapa.java
new file mode 100644 (file)
index 0000000..246191b
--- /dev/null
@@ -0,0 +1,78 @@
+public class Mapa {\r
+       public final static int IZLAZ = -5;\r
+       public final static int ZID = -1;\r
+       public final static int ERROR = Integer.MIN_VALUE;\r
+\r
+       private int visina, sirina;\r
+       private int[][] mat;\r
+       private boolean[][] pos;\r
+\r
+       public int getSirina() {\r
+               return sirina;\r
+       }\r
+\r
+       public int getVisina() {\r
+               return visina;\r
+       }\r
+\r
+       public void setPos(int x, int y, boolean b) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       pos[x][y] = b;\r
+               }\r
+       }\r
+\r
+       public boolean getPos(int x, int y) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       return pos[x][y];\r
+               } else {\r
+                       return true;\r
+               }\r
+       }\r
+\r
+       public int getMat(int x, int y) {\r
+               if (0 <= x && x < sirina && 0 <= y && y < visina) {\r
+                       return mat[x][y];\r
+               } else {\r
+                       return ERROR;\r
+               }\r
+       }\r
+\r
+       public Mapa(int sirina, int visina) {\r
+               this.sirina = sirina;\r
+               this.visina = visina;\r
+               mat = new int[sirina][visina];\r
+               pos = new boolean[sirina][visina];\r
+       }\r
+\r
+       public static Mapa ucitajIzFajla(String imeFajla) {\r
+               if (!Svetovid.testIn(imeFajla)) {\r
+                       return null;\r
+               }\r
+\r
+               int sirina = Svetovid.in(imeFajla).readInt();\r
+               int visina = Svetovid.in(imeFajla).readInt();\r
+               if (sirina >= 0 && visina >= 0) {\r
+                       Mapa res = new Mapa(sirina, visina);\r
+                       for (int j = 0; j < visina; j++)\r
+                               for (int i = 0; i < sirina; i++)\r
+                                       res.mat[i][j] = Svetovid.in(imeFajla).readInt();\r
+                       Svetovid.closeIn(imeFajla);\r
+                       return res;\r
+               } else {\r
+                       Svetovid.closeIn(imeFajla);\r
+                       return null;\r
+               }\r
+       }\r
+\r
+       public void stampaj() {\r
+               if (visina != 0 && sirina != 0) {\r
+                       System.out.println(visina + " " + sirina);\r
+                       for (int j = 0; j < visina; j++) {\r
+                               for (int i = 0; i < sirina; i++) {\r
+                                       System.out.print(mat[i][j] + "\t");\r
+                               }\r
+                               System.out.println();\r
+                       }\r
+               }\r
+       }\r
+}\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/Polje.java b/PretrazivanjeSaVracanjem/Lavirint/Polje.java
new file mode 100644 (file)
index 0000000..a037c37
--- /dev/null
@@ -0,0 +1,30 @@
+/**\r
+ * Klasa Polje se koristi za pamcenje x i y koordinata nekog polja, kao i\r
+ * vrednosti na toj poziciji u mapi\r
+ */\r
+\r
+public class Polje {\r
+       private int x, y, v;\r
+\r
+       Polje(int x, int y, int v) {\r
+               this.x = x;\r
+               this.y = y;\r
+               this.v = v;\r
+       }\r
+\r
+       public int getX() {\r
+               return x;\r
+       }\r
+\r
+       public int getY() {\r
+               return y;\r
+       }\r
+\r
+       public int getV() {\r
+               return v;\r
+       }\r
+\r
+       public String toString() {\r
+               return x + " " + y + " " + v;\r
+       }\r
+}
\ No newline at end of file
diff --git a/PretrazivanjeSaVracanjem/Lavirint/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/Resenje.java
new file mode 100644 (file)
index 0000000..5732427
--- /dev/null
@@ -0,0 +1,80 @@
+/**\r
+ * Klasa Resenje koristi se za pamcenje pronadjenog puta.\r
+ * \r
+ * Polje Polja se koristi za pamcenje svih polja na putu.\r
+ * \r
+ * Polje nepromenljivaListaPolja je dodata da se omoguci\r
+ * pristup poljima resenja "spolja" (za proveru kvaliteta puta na primer), \r
+ * ali tako da ne moze da se utice na sam sadrzaj te liste.\r
+ */\r
+import java.util.ArrayList;\r
+import java.util.List;\r
+import java.util.Collections;\r
+\r
+public class Resenje implements Cloneable {\r
+       private ArrayList<Polje> polja;\r
+       private List<Polje> nepromenljivaListaPolja;\r
+\r
+       Resenje() {\r
+               polja = new ArrayList<Polje>();\r
+               nepromenljivaListaPolja = Collections.unmodifiableList(polja);\r
+       }\r
+\r
+       // Dodaje pulje u resenje\r
+       public void dodaj(int x, int y, int v) {\r
+               polja.add(new Polje(x, y, v));\r
+       }\r
+\r
+       // Izbacuje polje iz resenja\r
+       public void izbaciKraj() {\r
+               if (getLength() > 0) {\r
+                       polja.remove(getLength() - 1);\r
+               } else {\r
+                       System.err.println("greska: resenje je vec prazno");\r
+               }\r
+       }\r
+\r
+       // Stampa resenje\r
+       public void stampaj() {\r
+               System.out.println(getLength());\r
+               for (int i = 0; i < getLength(); i++)\r
+                       System.out.println(polja.get(i));\r
+       }\r
+\r
+       // Vraca duzinu resenja\r
+       public int getLength() {\r
+               return polja.size();\r
+       }\r
+\r
+       // Vraca i-to polje na putu. Ne koristi se u ovoj verziji zadatka.\r
+       // Moze se koristiti za proveru kvaliteta resenja\r
+       public Polje getPolje(int i) {\r
+               return polja.get(i);\r
+       }\r
+\r
+       // Vraca sva polja na putu. Ne koristi se u ovoj verziji zadatka.\r
+       // Moze se koristiti za proveru kvaliteta resenja\r
+       public List<Polje> getPolja() {\r
+               return nepromenljivaListaPolja;\r
+       }\r
+\r
+       // Kreira klon od resenja\r
+       @Override\r
+       public Resenje clone() {\r
+               Resenje rez = new Resenje();\r
+               for (Polje p : polja) {\r
+                       rez.dodaj(p.getX(), p.getY(), p.getV());\r
+               }\r
+               return rez;\r
+       }\r
+\r
+       // Vraca vrednost puta\r
+       // Vrednost se definise kao zbir svih vrednosti polja na putu\r
+       public int getVrednost() {\r
+               int rez = 0;\r
+               for (Polje p : polja) {\r
+                       rez = rez + p.getV();\r
+               }\r
+               return rez;\r
+       }\r
+}\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/blago1.txt b/PretrazivanjeSaVracanjem/Lavirint/blago1.txt
new file mode 100644 (file)
index 0000000..5105c10
--- /dev/null
@@ -0,0 +1,5 @@
+5 4\r
+ 0  0  5  0  0\r
+ 0  4 -1  0  0\r
+ 0  1 -1 -1 -1\r
+ 5  0  0  0 -5\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/blago2.txt b/PretrazivanjeSaVracanjem/Lavirint/blago2.txt
new file mode 100644 (file)
index 0000000..7bfb346
--- /dev/null
@@ -0,0 +1,6 @@
+5 5\r
+ 0  0  0 -1 -5 \r
+ 7 -1  0 -1  0\r
+ 0 -1  3  3  5\r
+ 0 -1  1 -1  0\r
+-1 -1 15  0  0\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/blago3.txt b/PretrazivanjeSaVracanjem/Lavirint/blago3.txt
new file mode 100644 (file)
index 0000000..28a830e
--- /dev/null
@@ -0,0 +1,10 @@
+8 9\r
+ 0  0  0  4  0  2  0  0\r
+-1 -1 -1 -1 -1 -1  0 -1\r
+ 0  4  0  3  0  0  0 -1\r
+ 0  2  5  1  0  6  0 -1\r
+ 0 -1 -1 -1  0  0 12 -1\r
+ 0 10 -5  1 -1  0  0 -1\r
+-1 -1 -1  0  0  6  0  1\r
+ 0 -1 20  0 -1  0 -1  0\r
+-1 -1  0  15 0  0 -1 99\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/l-prazan.txt b/PretrazivanjeSaVracanjem/Lavirint/l-prazan.txt
new file mode 100644 (file)
index 0000000..cc98c8e
--- /dev/null
@@ -0,0 +1,4 @@
+3 3\r
+ 0  0  0\r
+ 0  0  0\r
+ 0  0 -5\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/l1.txt b/PretrazivanjeSaVracanjem/Lavirint/l1.txt
new file mode 100644 (file)
index 0000000..3b92da0
--- /dev/null
@@ -0,0 +1,5 @@
+5 4\r
+ 0  0  0  0  0\r
+ 0  0 -1  0  0\r
+ 0  0 -1 -1 -1\r
+ 0  0  0  0 -5\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/l2.txt b/PretrazivanjeSaVracanjem/Lavirint/l2.txt
new file mode 100644 (file)
index 0000000..28796c0
--- /dev/null
@@ -0,0 +1,6 @@
+5 5\r
+ 0  0  0 -1 -5 \r
+ 0 -1  0 -1  0\r
+ 0 -1  0  0  0\r
+ 0 -1  0 -1  0\r
+-1 -1  0  0  0\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/l3.txt b/PretrazivanjeSaVracanjem/Lavirint/l3.txt
new file mode 100644 (file)
index 0000000..fb1f4e4
--- /dev/null
@@ -0,0 +1,10 @@
+8 9\r
+ 0  0  0  0  0  0  0  0\r
+-1 -1 -1 -1 -1 -1  0 -1\r
+ 0  0  0  0  0  0  0 -1\r
+ 0  0  0  0  0  0  0 -1\r
+ 0 -1 -1 -1  0  0  0 -1\r
+ 0  0 -5  0 -1  0  0 -1\r
+-1 -1 -1  0  0  0  0  0\r
+ 0 -1  0  0 -1  0 -1  0\r
+-1 -1  0  0  0  0 -1  0\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/l4.txt b/PretrazivanjeSaVracanjem/Lavirint/l4.txt
new file mode 100644 (file)
index 0000000..444dab5
--- /dev/null
@@ -0,0 +1,11 @@
+10 10\r
+ 0  0  0  0  0  0  0  0  0  0\r
+ 0 -1 -1 -1 -1 -1 -1 -1  0 -1\r
+ 0 -1  0  0  0  0  0 -1  0 -1\r
+ 0 -1  0 -1  0 -1  0 -1  0 -1\r
+ 0 -1  0 -1  0 -1  0 -1  0 -1\r
+ 0 -1  0  0 -5 -1  0 -1  0 -1\r
+ 0  0  0 -1 -1  0  0 -1  0  0\r
+ 0  0  0 -1  0  0 -1  0  0  0\r
+-1 -1  0 -1  0  0  0  0 -1  0\r
+ 0  0  0  0  0  0  0  0 -1  0\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/lav.txt b/PretrazivanjeSaVracanjem/Lavirint/lav.txt
new file mode 100644 (file)
index 0000000..e32db19
--- /dev/null
@@ -0,0 +1,7 @@
+5 6\r
+ 0  0  0 -1 -5\r
+ 0 -1  0 -1  0\r
+ 0 -1  0  0  0\r
+ 0 -1  0 -1  0\r
+-1 -1  0  0  0\r
+ 0 -1  0  0 -1\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/lavblok.txt b/PretrazivanjeSaVracanjem/Lavirint/lavblok.txt
new file mode 100644 (file)
index 0000000..ee5fe19
--- /dev/null
@@ -0,0 +1,4 @@
+3 3\r
+ 0  0  0\r
+ 0 -1 -1\r
+ 0 -1 -5\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/readme.txt b/PretrazivanjeSaVracanjem/Lavirint/readme.txt
new file mode 100644 (file)
index 0000000..cb7d47d
--- /dev/null
@@ -0,0 +1,11 @@
+Pri koristicenju programa moguce je koristiti sledece fajlove:\r
+\r
+lav.txt - sadrzi lavirint koji se moze koristiti za proveru da\r
+li postoji put, ispis puta i ispis najkraceg puta.\r
+\r
+lavblok.txt - sadrzi lavirint u kojem ne postoji put\r
+\r
+l1.txt, l2.txt, l3.txt, l4.txt sadrze razlicite resive lavirinte.\r
+\r
+blago1.txt, blago2.txt i blago3.txt - sadrzi lavirinte sa blagom \r
+za testiranje najvrednijeg puta.\r
diff --git a/PretrazivanjeSaVracanjem/Lavirint/zadatak-lavirint.txt b/PretrazivanjeSaVracanjem/Lavirint/zadatak-lavirint.txt
new file mode 100644 (file)
index 0000000..5581283
--- /dev/null
@@ -0,0 +1,57 @@
+Zadatak - pretrazivanje sa vracanjem - lavirint\r
+============================================================\r
+\r
+Napisati program koji ucitava lavirint iz fajla i nalazi put\r
+ili puteve sa odredjenim osobinama.\r
+\r
+\r
+Format fajla\r
+------------------------------------------------------------\r
+\r
+Lavirint je u fajlu predstavljen na sledeci nacin:\r
+\r
+U prvom redu se nalaze dva broja S i V (1<= S, V <=10), koji\r
+predstavljaju sirinu i visinu lavirinta. U sledecih V redova\r
+se nalaze po S celih brojeva koji predstavljaju lavirint.\r
+Brojevi imaju sledece znacenje:\r
+\r
+ 0 - prazno polje\r
+-1 - zid, na ovo polje se ne moze stupiti\r
+-5 - izlaz iz lavirinta\r
+\r
+Sa jednog polja se moze preci na drugo, ukoliko imaju\r
+zajednicku stranicu, odnosno mozemo preci na polje levo,\r
+desno, gore ili dole.\r
+\r
+Pri ucitavanju pretpostaviti da ukoliko fajl postoji da su\r
+podaci u njemu ispravno zadati.\r
+\r
+\r
+Zadatak\r
+------------------------------------------------------------\r
+\r
+- Napisati program tako da proverava da li postoji put od\r
+pocetnog polja do izlaza iz lavirinta. Pocetno polje je na\r
+koordinatama 1,1, odnosno u gornjem levom uglu.\r
+\r
+- Program prosiriti tako da na ekran ispisuje trazeni put\r
+(ako postoji).\r
+\r
+- Modifikovati program tako da vraca najkraci put do\r
+izlaza.\r
+\r
+- Razmotriti sledecu modifikaciju problema: \r
+\r
+U drevnim lavirintima se nalaze zlatnici razasuti po\r
+poljima. Ovi lavirinti su veoma opasni, pa ih nije\r
+jednostavno pokupiti, vec se to moze raditi samo pomocu\r
+specijalnih robota. Na srecu pronadjene su mape koje\r
+precizno pokazuju kako lavirinti izgledaju, gde su im izlazi\r
+i koliko zlatnika se moze pokupiti na kom polju. Sada treba\r
+naci put kroz lavirint tako da se pokupi sto vise zlatnika,\r
+a da se pri tome ne nagazi na isto polje dva puta.\r
+\r
+Pri ucitavanju lavirinta, bilo koji pozitivan broj\r
+predstavlja broj zlatnika na tom polju. Program treba da\r
+vraca optimalni put do izlaza, odnosno takav da se pokupi\r
+sto vise zlatnika na putu.\r
Svarog.pmf.uns.ac.rs/gitweb maintanance Doni Pracner