From 3c24990b2b5db35d728a4a706ba4963d3c936a76 Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Sun, 4 Dec 2016 20:09:25 +0100 Subject: [PATCH] Doterivanja objedinjenog resenja za lavirint --- .../Lavirint/ObjedinjenoResenje/Lavirint.java | 70 +++++++++---------- .../Lavirint/ObjedinjenoResenje/Mapa.java | 37 ++++++---- .../Lavirint/ObjedinjenoResenje/Resenje.java | 35 ++++++++-- 3 files changed, 89 insertions(+), 53 deletions(-) diff --git a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Lavirint.java b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Lavirint.java index 4fd8f79..312fa9c 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Lavirint.java +++ b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Lavirint.java @@ -34,23 +34,22 @@ public class Lavirint { } 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; } + 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 @@ -78,16 +77,15 @@ public class Lavirint { 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; } + 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 @@ -125,19 +123,21 @@ public class Lavirint { if (m.getMat(x, y) == Mapa.IZLAZ) { r.dodaj(x, y, 0); if (optResenje == null || c.compare(r, optResenje) < 0) { - optResenje = r.clone(); + optResenje = r.kopija(); } 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(); + return; } + + // pokusavamo da trazimo dalje put + 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(); } } diff --git a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Mapa.java b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Mapa.java index 246191b..243ca68 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Mapa.java +++ b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Mapa.java @@ -44,24 +44,31 @@ public class Mapa { pos = new boolean[sirina][visina]; } - public static Mapa ucitajIzFajla(String imeFajla) { + public Mapa(String imeFajla) { if (!Svetovid.testIn(imeFajla)) { - return null; + throw new RuntimeException("Fajl za kreiranje mape (" + + imeFajla + ") nije prisupacan"); } - 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); + sirina = Svetovid.in(imeFajla).readInt(); + visina = Svetovid.in(imeFajla).readInt(); + 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); + } + + public static Mapa ucitajIzFajla(String imeFajla) { + if (!Svetovid.testIn(imeFajla)) { return null; } + + return new Mapa(imeFajla); + } public void stampaj() { @@ -75,4 +82,8 @@ public class Mapa { } } } + + public String toString() { + return "Mapa velicine " + sirina + " x " + visina; + } } diff --git a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Resenje.java b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Resenje.java index 5732427..ffb2622 100644 --- a/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Resenje.java +++ b/PretrazivanjeSaVracanjem/Lavirint/ObjedinjenoResenje/Resenje.java @@ -11,14 +11,26 @@ import java.util.ArrayList; import java.util.List; import java.util.Collections; -public class Resenje implements Cloneable { +public class Resenje { private ArrayList polja; private List nepromenljivaListaPolja; - Resenje() { + public Resenje() { polja = new ArrayList(); nepromenljivaListaPolja = Collections.unmodifiableList(polja); } + + /** + Pravi novo resenje sa istim sadrzajem kao original + */ + public Resenje(Resenje original) { + // pozovemo "podrazumevani" konstruktor + this(); + // iskopiramo sva polja iz originala + for (Polje p : original.getPolja()) { + dodaj(p.getX(), p.getY(), p.getV()); + } + } // Dodaje pulje u resenje public void dodaj(int x, int y, int v) { @@ -40,6 +52,20 @@ public class Resenje implements Cloneable { for (int i = 0; i < getLength(); i++) System.out.println(polja.get(i)); } + + public String toString() { + StringBuilder sb = new StringBuilder(); + sb.append("Resenje: [ "); + if (getLength()>0) { + sb.append(polja.get(0)); + for (int i = 1; i < getLength(); i++) { + sb.append(", " + polja.get(i)); + } + } + sb.append(" ]"); + + return sb.toString(); + } // Vraca duzinu resenja public int getLength() { @@ -58,9 +84,8 @@ public class Resenje implements Cloneable { return nepromenljivaListaPolja; } - // Kreira klon od resenja - @Override - public Resenje clone() { + // Kreira nezavisnu kopiju ovog resenja + public Resenje kopija() { Resenje rez = new Resenje(); for (Polje p : polja) { rez.dodaj(p.getX(), p.getY(), p.getV()); -- 2.25.1