Zdrojový kód k 3. prednáške

/**
 * Trieda zapuzdrujuca spajany zoznam a manipulaciu s nim
 */
public class SpajanyZoznam {

        /**
         * Sukromna trieda reprezentujuca jeden uzol spajaneho zoznamu
         */
        private static class Uzol {
                int hodnota;
                Uzol dalsi;
        }

        /**
         * Referencia na prvy uzol spajaneho zoznamu
         */
        private Uzol prvy = null;

        /**
         * Prida novu hodnotu na zaciatok spajaneho zoznamu
         * @param hodnota pridavana hodnota
         */
        public void pridajNaZaciatok(int hodnota) {
                Uzol pridavany = new Uzol();
                pridavany.hodnota = hodnota;
                pridavany.dalsi = prvy;
                prvy = pridavany;
        }

        @Override
        public String toString() {
                String vysledok = "[";
                Uzol aktualny = prvy;
                while (aktualny != null) {
                        if (aktualny != prvy)
                                vysledok += ", ";

                        vysledok += aktualny.hodnota;
                        aktualny = aktualny.dalsi;
                }

                return vysledok + "]";
        }

        /**
         * Vrati sucet hodnot ulozenych v spajanom zozname
         */
        public int sucet() {
                // Referencia na uzol zoznamu, na ktorom sa prave nachadzame
                Uzol aktualny = prvy;
                // Premenna, v ktorej akumulujeme sucet
                int vysledok = 0;
                // Kym sme na nejakom uzle ...
                while (aktualny != null) {
                        // Priratame hodnotu uzla
                        vysledok += aktualny.hodnota;
                        // Presunieme sa na dalsi uzol v zozname
                        aktualny = aktualny.dalsi;
                }

                return vysledok;
        }       
}

import java.util.*;

public class Zasobnik {

        public static boolean spravneOzatvorkovany(String vyraz) {
                Stack<Character> zasobnik = new Stack<Character>();

                for (int i=0; i<vyraz.length(); i++) {
                        char znak = vyraz.charAt(i);
                        if ((znak == '(') || (znak == '['))
                                zasobnik.push(znak);

                        if (znak == ')') {
                                if (zasobnik.isEmpty())
                                        return false;

                                if (zasobnik.pop() != '(')
                                        return false;
                        }

                        if (znak == ']') {
                                if (zasobnik.isEmpty())
                                        return false;

                                if (zasobnik.pop() != '[')
                                        return false;
                        }
                }

                return zasobnik.isEmpty();
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                Scanner s = new Scanner(System.in);
                while (s.hasNextLine()) {
                        System.out.println(spravneOzatvorkovany(s.nextLine()));
                }
        }
}

import java.awt.Color;
import java.awt.event.MouseEvent;
import java.util.*;

import sk.upjs.jpaz2.*;

/**
 * JPAZ aplikacia demonstrujuca prehladavanie do sirky v 2D poli
 */
public class Bludisko extends WinPane {

        /**
         * Privatna na ulozenie suradnic policka (riadok, stlpec)
         */
        private static class Policko {
                int riadok;
                int stlpec;

                public Policko(int riadok, int stlpec) {
                        this.riadok = riadok;
                        this.stlpec = stlpec;
                }
        }

        /**
         * Informacia o obsadenosti policok. false - volne/true - prekazka
         */
        private boolean[][] bludisko = new boolean[10][10];

        /**
         * Suradnice cieloveho policka
         */
        private Policko ciel = null;

        /**
         * Predpripravene 2D pole so suradnicami posunutia pre uvazovane 4 smery
         */
        private int[][] smery = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        /**
         * Konstruktor, ktory len nakresli mriezku
         */
        public Bludisko() {
                kresliBludisko();
        }

        /**
         * Metoda, ktora nakresli do kresliacej plochy aktualny stav bludiska
         */
        private void kresliBludisko() {
                // Vymazeme kresliacu plochu
                clear();

                // Vytvorime korytnacku na kreslenie
                Turtle kreslicka = new Turtle();
                kreslicka.setVisible(false);
                add(kreslicka);

                // Nakreslime horizontalne a vertikalne ciary
                for (int i = 0; i < 10; i++) {
                        kreslicka.setPosition(0, i * 30);
                        kreslicka.moveTo(300, i * 30);
                        kreslicka.setPosition(i * 30, 0);
                        kreslicka.moveTo(i * 30, 300);
                }

                // Prechadzame polickami a policka s prekazkami zasedime
                for (int i = 0; i < 10; i++)
                        for (int j = 0; j < 10; j++) {
                                if (bludisko[i][j]) {
                                        kreslicka.setPosition(j * 30 + 1, i * 30 + 1);
                                        kreslicka.setDirection(90);
                                        kreslicka.openPolygon();
                                        kreslicka.setFillColor(Color.gray);
                                        for (int k = 0; k < 4; k++) {
                                                kreslicka.step(29);
                                                kreslicka.turn(90);
                                        }
                                        kreslicka.closePolygon();
                                }              
                        }

                // Na policko, ktore je oznacene ako ciel nakreslime cervenu bodku
                if (ciel != null) {
                        kreslicka.setPosition(ciel.stlpec * 30 + 15, ciel.riadok * 30 + 15);
                        kreslicka.setFillColor(Color.red);
                        kreslicka.dot(10);
                }

                // Odstranime kresliacu korytnacku z plochy
                remove(kreslicka);
        }

        /**
         * Dokresli do jednotlivych policok ich vzdialenosti od startoveho policka
         * @param vzdialenosti pole so vzdialenostami pre jednotlive policka
         */
        private void zobrazVzdialenosti(int[][] vzdialenosti) {
                // Vytvorime korytnacku na kreslenie a pridame ju do plochy
                Turtle kreslicka = new Turtle();
                kreslicka.setVisible(false);
                add(kreslicka);
                kreslicka.setDirection(90);

                // Prechadzame vsetkymi polickami a pre tie, ktorych hodnota nie je -1
                // vypiseme informaciu o vzdialenosti
                for (int i = 0; i < 10; i++)
                        for (int j = 0; j < 10; j++)
                                if (vzdialenosti[i][j] != -1) {
                                        kreslicka.setPosition(j * 30 + 10, i * 30 + 20);
                                        kreslicka.print(Integer.toString(vzdialenosti[i][j]));
                                }              

                // Odstranime kresliacu korytnacku z plochy
                remove(kreslicka);
        }

        /**
         * Prefarbi policka cesty zltou farbou
         * @param cesta zoznam suradnic policok cesty
         */
        private void zobrazCestu(List<Policko> cesta) {
                if (cesta == null)
                        return;

                // Vytvorime kresliacu korytnacku
                Turtle kreslicka = new Turtle();
                kreslicka.setVisible(false);
                add(kreslicka);
                kreslicka.setFillColor(Color.yellow);

                // Prechadzame polickami v ceste a kazde policko podfarbime zltou farbou
                for (int i=0; i<cesta.size(); i++) {
                        kreslicka.setPosition(cesta.get(i).stlpec * 30 + 1, cesta.get(i).riadok * 30 + 1);
                        kreslicka.setDirection(90);
                        kreslicka.openPolygon();
                        for (int k = 0; k < 4; k++) {
                                kreslicka.step(29);
                                kreslicka.turn(90);
                        }
                        kreslicka.closePolygon();
                }

                // Odstranime kresliacu korytnacku z plochy
                remove(kreslicka);
        }

        /**
         * Vrati, ci policko so zadanymi suradnicami existuje a je volne
         */
        private boolean volnePolicko(Policko policko) {
                if ((policko.riadok < 0) || (policko.riadok >= 10) || (policko.stlpec < 0) || (policko.stlpec >= 10))
                        return false;

                return (!bludisko[policko.riadok][policko.stlpec]);
        }

        @Override
        protected void onMousePressed(int x, int y, MouseEvent detail) {
                int riadok = y / 30;
                int stlpec = x / 30;

                // Overime, ci sme vobec klikli na nejake policko
                if ((riadok < 0) || (riadok >= 10) || (stlpec < 0) || (stlpec >= 10))
                        return;

                // Ak nie je zatlaceny alt, tak alebo oznacujeme prekazku alebo presuvame ciel
                if (!detail.isAltDown()) {
                        // Ciel zmenime ak sa kliklo lavym tlacidlom a zaroven policko, na ktore sa kliklo je volne
                        if ((detail.getButton() == MouseEvent.BUTTON1) && (volnePolicko(new Policko(riadok, stlpec))))
                                ciel = new Policko(riadok, stlpec);

                        // Ak sa kliklo pravym tlacidlom mysi, tak menime to, ci na policku je prekazka
                        if (detail.getButton() == MouseEvent.BUTTON3) {
                                bludisko[riadok][stlpec] = !bludisko[riadok][stlpec];

                                // Ak sa kliklo na policko s cielom, tak ho odstranime
                                if ((ciel != null) && (ciel.riadok == riadok) && (ciel.stlpec == stlpec))
                                        ciel = null;
                        }

                        // Po zmenach nechame prekreslit bludisko
                        kresliBludisko();
                } else {
                        // Ak sa kliklo lavym tlacidlom mysi, tak spustime hladanie najkratsej cesty z policka,
                        // na ktore sme klikli do cieloveho policka
                        if (detail.getButton() == MouseEvent.BUTTON1)
                                najdiNajkratsiuCestu(new Policko(riadok, stlpec));
                }
        }

        /**
         * Najde a zobrazi najkratsiu cestu medzi cielovym polickom a zadanym startovym polickom
         * @param start
         */
        private void najdiNajkratsiuCestu(Policko start) {
                // Ak nie je ciel, niet co hladat
                if (ciel == null)
                        return;

                // Pre kazde policko vypocitame jeho vzdialenost od startovacieho policka
                int[][] vzdialenosti = poleVzdialenosti(start);
                List<Policko> najCesta = najdiSpojenie(start, ciel, vzdialenosti);

                // Nakreslime bludisko
                kresliBludisko();
                // Podfarbime najdenu cestu
                zobrazCestu(najCesta);
                // Vypiseme do kazdeho policka vzdialenosti
                zobrazVzdialenosti(vzdialenosti);
        }

        /**
         * Pre kazde policko v bludisku vypocita jeho vzdialenost od startovacieho policka
         * @param start
         * @return
         */
        public int[][] poleVzdialenosti(Policko start) {
                // Vyrobime pole s vysledkami a inicializujeme ho hodnotami -1
                int[][] vzdialenost = new int[10][10];
                for (int i=0; i<10; i++)
                        for (int j=0; j<10; j++)
                                vzdialenost[i][j] = -1;
                // Startovacie policko ma vzdialenost 0 od startu
                vzdialenost[start.riadok][start.stlpec] = 0;

                // Vytvorime rad policok cakajucich na spracovanie
                Queue<Policko> rad = new LinkedList<Policko>();
                // Do radu pridame startovacie policko
                rad.offer(start);
                // Kym niekto caka v rade na spracovanie, tak spracuvame
                while (!rad.isEmpty()) {
                        // Vyberieme prveho cakajuceho v rade
                        Policko policko = rad.poll();

                        // Pozrieme sa na susedov vybraneho policka
                        for(int smer = 0; smer < 4; smer++) {
                                // Vypocitame suradnice suseda v skumanom smere s pouzitim pola smery
                                Policko sused = new Policko(policko.riadok + smery[smer][0], policko.stlpec + smery[smer][1]);

                                // Ak je susedne policko volne a platne a zaroven jeho vzdialenost je -1,
                                // t.j. zatial nebolo spracovavane, tak ho spracujeme
                                if (volnePolicko(sused) && (vzdialenost[sused.riadok][sused.stlpec] == -1)) {
                                        // Policko je vzdialene o 1 dalej ako jeho sused
                                        vzdialenost[sused.riadok][sused.stlpec] = vzdialenost[policko.riadok][policko.stlpec] + 1;
                                        // Zaradime policko do radu na spracovanie jeho susedov
                                        rad.offer(sused);
                                }              
                        }
                }

                return vzdialenost;
        }

        /**
         * S vyuzitim pola najkratsich vzdialenosti najde najkratsiu cestu zo startovacieho policka do cieloveho
         */
        private List<Policko> najdiSpojenie(Policko start, Policko ciel, int[][] vzdialenosti) {
                // Ak do cieloveho policka sa nenasla cesta, tak koncime
                if (vzdialenosti[ciel.riadok][ciel.stlpec] == -1)
                        return null;

                // Vyrobime si zoznam na zapisovanie policok cesty
                List<Policko> cesta = new ArrayList<Policko>();
                // Spatny prechod zaciname od cieloveho policka
                Policko policko = ciel;
                // Kym neprideme na policko vo vzdialenosti 0, t.j. na startovacie policko, tak budujeme cestu
                while (vzdialenosti[policko.riadok][policko.stlpec] != 0) {
                        // Aktualne policko pridame do cesty
                        cesta.add(policko);
                        // Ulozime si aktualnu vzdialenosti do startovacieho policka
                        int aktualnaVzdialenost = vzdialenosti[policko.riadok][policko.stlpec];
                        // Hladame susedne policko, ktore je k startovaciemu policko o 1 blizsie
                        for (int smer=0; smer<4; smer++) {
                                Policko sused = new Policko(policko.riadok + smery[smer][0], policko.stlpec + smery[smer][1]);
                                if (volnePolicko(sused) && (vzdialenosti[sused.riadok][sused.stlpec] == aktualnaVzdialenost-1)) {
                                        // Nasli sme dobreho suseda, takze si ho zapamatame pre dalsiu iteraciu while-u
                                        policko = sused;
                                        break;
                                }
                        }
                }
                // Policko, na ktorom sme skoncili pridame do cesty
                cesta.add(policko);

                // Vratime cestu, ktoru sme spatnym prechodom vybudovali
                return cesta;
        }

        /**
         * Spustacia main metoda
         * @param args
         */
        public static void main(String[] args) {
                Bludisko bludisko = new Bludisko();
        }
}