// L?sningsforslag, inf110, uke 11b. // ------------------------------------------------------------------ /* * Antar at hvert rom i labyrinten er firkantet og har maksimalt 4 * utganger, til nord (naborom[0]), s?r (naborom[2]), ?st (naborom[1]) * og vest (naborom[3]). */ class Rom { String navn; Rom[] naborom = new Rom[4]; boolean skatt = false; // Skal v?re true i rommet med skatten... boolean merke = false; // Variable som brukes for ? finne en raskere vei til skatten. int avstand = Integer.MAX_VALUE; Rom vei, direkteVei; } public class Labyrint { public static void main(String[] args) { Rom inngang; // Inngangen til labyrinten. //ENTEN: let(inngang, 2); // 2: Kommer fra s?r, inngang mot nord... // ELLER: //let2(inngang); //skrivVei(inngang, 2); } /* * Metode som ligner veldig p? den som ble forelest. * For ? kunne sjekke naborommene i rekkef?lgen venstre-rettfrem-h?yre, * er det n?dvendig ? vite hvilket rom vi kom fra. * (fra + 1) % 4 gir rommet til venstre etter at vi har g?tt inn, * (fra + 2) % 4 gir rommet rett frem, * (fra + 3) % 4 gir rommet til h?yre. * N?r vi kaller videre for neste rom, kommer vi fra motsatt retning av * det vi g?r, det vil si (fra + <1 eller 2 eller 3> + 2) % 4. */ public static boolean let(Rom r, int fra) { boolean funnet = false; System.out.println("G? inn i rommet foran deg."); funnet = r.skatt; if (funnet) { System.out.println("Plukk opp skatten"); System.out.println("Rygg ut av rommet."); } else { r.merke = true; System.out.println("Snu deg til venstre."); for (int retning = 1; retning <= 3; retning++) { if (!funnet && !(r.naborom[(retning + fra) % 4] == null) && !r.naborom[(retning + fra) % 4].merke) { funnet = let(r.naborom[(retning + fra) % 4], (retning + fra + 2) % 4); } System.out.println("Snu deg til h?yre."); } System.out.println("G? ut av rommet."); System.out.println("Snu deg rundt."); } return funnet; } /* * Metoden som bruker (uvektet) korteste-vei algoritme for ? * finne frem til skatten. * N?r rommet med skatten tas ut av k?en (velges som kjent), vet * vi den raskeste veien fra inngangen og dit. * For ? f? til en enkel utskrift, kalles da metoden settDirekteVei * som setter den "intuitive" veien i hver node, det vil si veien _mot_ * skatten (i motsetning til vei-variablen i algoritmen som setter * hvordan veien bakfra, hvordan vi kom _inn_ i rommet). */ public static boolean let2(Rom start) { Koe k = new Koe(); // Vanlig (FIFO-)k?. start.avstand = 0; k.insert(start); while (!k.isEmpty()) { Rom r = k.taUt(); r.merke = true; if (r.skatt) { settDirekteVei(r); // Har funnet skatten, trenger ikke ? s?ke videre. return true; } for (int i = 0; i < 4; i++) { if (r.naborom[i] != null && !r.naborom[i].merke) { r.naborom[i].avstand = r.avstand+1; r.naborom[i].vei = r; k.insert(r.naborom[i]); } } } return false; } static void settDirekteVei(Rom rr) { if (rr.vei != null) { rr.vei.direkteVei = rr; settDirekteVei(rr.vei); } } /* * Metoden som dirigerer veien gjennom labyrinten etter at den raskeste * veien ? g? er satt i variabelen direkteVei. * Beregningen av venstre/h?yre er som for den f?rste let-metoden. */ static void skrivVei(Rom r, int fra) { System.out.println("G? inn i rommet foran deg."); if (r.skatt) { System.out.println("Plukk opp skatten"); System.out.println("Snu deg rundt og g? ut igjen."); } else { if (r.direkteVei != null) { if (r.direkteVei == r.naborom[(fra + 1) % 4]) { System.out.println("Snu til venstre"); skrivVei(r.naborom[(fra + 1) % 4], (fra + 3) % 4); System.out.println("Snu til h?yre og g? ut."); } else if (r.direkteVei == r.naborom[(fra + 3) % 4]) { System.out.println("Snu til h?yre"); skrivVei(r.naborom[(fra + 3) % 4], (fra + 5) % 4); System.out.println("Snu til venstre og g? ut."); } else { skrivVei(r.naborom[(fra + 2) % 4], (fra + 4) % 4); System.out.println("G? rett frem ut av rommet."); } } } } }