Pojednostavljivanje resenja za NajboljiPut

[spa2-materijali.git] / PretrazivanjeSaVracanjem / Lavirint / NajboljiPut / NajboljiPut.java

/**
 * Klasa NajboljiPut sadrzi nekoliko metoda za trazenje puteva.
 * 
 * Klase KomparatorPoDuzini i KomparatorPoVrednosti predstavljaju komparatore
 * koji se korste pri trazenju najkraceg i najvrednijeg puta.
 */

import java.util.Comparator;

public class NajboljiPut {

        // Konstante za polja u mapi
        public final static int IZLAZ = -99;
        public final static int ZID = -11;

        // interno predstavljanje mape
        private int visina, sirina;
        private int[][] mat;
        // matrica posecenih polja
        private boolean[][] pos;

        // Polje optResenje sluzi za pamcenje optimalnog resenja
        private Put optResenje;

        // Ucitava mapu iz datog fajla i stampa je na ekran
        NajboljiPut(String imeFajla) {
                if (!Svetovid.testIn(imeFajla)) {
                        throw new RuntimeException("Fajl za kreiranje mape (" + imeFajla + ") nije prisupacan");
                }

                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);

                stampajMapu();
        }

        private void stampajMapu() {
                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();
                        }
                }
        }

        // 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 Put najkraciPut(int x, int y) {
                Put r = new Put();
                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 Put najvrednijiPut(int x, int y) {
                Put r = new Put();
                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, Put r, Comparator<Put> c) {
                if (x < 0 || x >= sirina || y < 0 || y >= visina) {
                        return;
                }
                if (pos[x][y]) {
                        return;
                }
                if (mat[x][y] == ZID) {
                        return;
                }
                if (mat[x][y] == IZLAZ) {
                        r.dodaj(x, y, 0);
                        if (optResenje == null || c.compare(r, optResenje) < 0) {
                                optResenje = r.kopija();
                        }
                        r.izbaciKraj();
                        return;
                }

                // pokusavamo da trazimo dalje put
                pos[x][y] = true;
                r.dodaj(x, y, mat[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);
                pos[x][y] = false;
                r.izbaciKraj();
        }

        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;
                }

                NajboljiPut l = new NajboljiPut(fajl);
                Put r;

                System.out.println("Unesite koordinate za pocetak:");
                System.out.println("x?");
                int x = Svetovid.in.readInt();
                System.out.println("y?");
                int y = Svetovid.in.readInt();

                System.out.println("Najkraci put je:");
                r = l.najkraciPut(x, y);
                if (r != null) {
                        r.stampaj();
                } else {
                        System.out.println("Nema resenja");
                }

                System.out.println("Najvredniji put je:");
                r = l.najvrednijiPut(0, 0);
                if (r != null) {
                        r.stampaj();
                        System.out.println("Vrednost puta: " + r.getVrednost());
                } else {
                        System.out.println("Nema resenja");
                }
        }
}

// Komparator za resenja po duzini resenja
class KomparatorPoDuzini implements Comparator<Put> {
        public int compare(Put r1, Put r2) {
                return r1.getLength() - r2.getLength();
        }
}

// Komparator za resenja po vrednosti resenja
class KomparatorPoVredosti implements Comparator<Put> {
        public int compare(Put r1, Put r2) {
                return r2.getVrednost() - r1.getVrednost();
        }
}