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