From: Sasa Tosic <sashat@dmi.uns.ac.rs>
Date: Sat, 7 Nov 2015 20:58:15 +0000 (+0100)
Subject: Lavirint, primer pretrazivanja sa vracanjem za test
X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain;h=f734195b4c499d152fd3b996839668530fa3868b

Lavirint, primer pretrazivanja sa vracanjem za test
---

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<Resenje> 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<Resenje> {
+	public int compare(Resenje r1, Resenje r2) {
+		return r1.getLength() - r2.getLength();
+	}
+}
+
+// Komparator za resenja po vrednosti resenja
+class KomparatorPoVredosti implements Comparator<Resenje> {
+	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<Polje> polja;
+	private List<Polje> nepromenljivaListaPolja;
+
+	Resenje() {
+		polja = new ArrayList<Polje>();
+		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<Polje> 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.