// Zettel 11 | Jan Kellermann, Astrid Bertram, Gruppe 15 |	Tutorin: Susanne Richter

class Labyrinth2 {
	// Dies ist die erweiterte Variante, die alle Loesungen + kuerzesten Weg findet.

	static final boolean[][] gang = {	{ false, true, true,false,false,false },
										{ true ,false,false, true, true,false },
										{ true ,false, true,false, true,true  },
										{ false, true,false,false, true,false },
										{ false, true, true, true,false, true },
										{ false,false,false,false, true,false }};

	static final boolean[] ausgang =	{ false,false,false,false,false,true };

	static boolean[] marke = { false,false,false,false,false,false };
	static int[] logbuch = new int[6];
	static int[] shortway = new int[6];
	static int waycounter=0;
	static int shortest=6;

	public static void main(String[] argv) throws Exception {
		sucheAusweg(0,0);	// Starte am Punkt 0 und suche alle Wege zum Ausgang.
		// der 1. Parameter ist der Start-Punkt
		// der 2. Parameter ist die bisherige Schrittanzahl
	}

	static void sucheAusweg(int current, int steps) throws Exception {
		marke[current] = true;  // Marke setzen, hier war ich schon.
		logbuch[steps] = current;  // Weg ins Logbuch eintragen
		steps++;
		// nachfolgende Zeile zum Testen auskommentieren
		// System.out.println("seen "+current+" at "+steps+" Steps");
		if (ausgang[current]) {		//Wenn aktueller Punkt ein Ausgang
			System.out.print("Ausgang gefunden");
			for (int i=0; i<steps; i++)
				System.out.print(" - "+logbuch[i]);
			System.out.println();
			waycounter++;	// Einen Weg mehr gefunden
			if (shortest>steps) { // Wenn Weg kuerzer als bish. kuerzester
				for (int i=0; i<steps; i++)
					shortway[i]=logbuch[i]; // Weg kopieren
				shortest=steps;	// kuerzeste Weglaenge uebernehmen
			}
		}
		for (int i=0; i<gang.length; i++)
				// Wenn es einen Gang von hier nach i gibt UND
				// i noch nicht als besucht markiert ist
				// und i auch nicht als "nie wieder anspringen" markiert ist
			if (gang[current][i] && !marke[i])
				sucheAusweg(i,steps); // Versuchs doch mal von Punkt i aus
		steps--; // und wieder einen Schritt retoure, da nix weiter gefunden
		marke[current] = false; // Markierung "da war ich schonmal" loeschen
		logbuch[steps] = 0; // Eintrag aus Logbuch loeschen
		if (steps==0) {	// Wenn alle Moeglichkeiten durchgegangen,
			if (waycounter==0) {	// Wenn keinen Weg gefunden
				throw new Exception ("Hoppla, keinen Ausweg gefunden!");
			} else {
				System.out.print("Kuerzester Weg:");
				for (int i=0; i<shortest; i++)
					System.out.print(" - "+shortway[i]);
				System.out.println();
			}
		}
	}
}