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

class Labyrinth1 {
	// Diese Variante sucht auf effizentem Weg irgendeinen Ausgang
	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 boolean[] noway   =  { false,false,false,false,false,false };
	static int[] logbuch = new int[6];
	static int startpunkt,steps = 0;

	public static void main(String[] argv) throws Exception {
		sucheAusweg(startpunkt,0);
	}

	static void sucheAusweg(int current, int steps) throws Exception {
		marke[current] = true;  // Marke setzen, hier war ich schon.
		logbuch[steps] = current;
		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();
			System.exit(1);
		}
		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] && !noway[i])
				sucheAusweg(i,steps); // Versuchs doch mal von Punkt i aus
		marke[current] = false; // Marke ruecksetzen
		noway[current] = true; // Nie wieder anspringen, da aussichtslos.
		steps--;
		logbuch[steps] = 0; // Eintrag aus Logbuch loeschen
		if (current==startpunkt) // Wenn alle Möglichkeiten vom urspr. Startpunkt
							// durchgegangen sind,
			throw new Exception ("Hoppla, keinen Ausweg gefunden!");
	}
}