// 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.");
		}
	    }
	}
    }

}