public class Labyrinth {

	final static char C_WALL = 'X';
	final static char C_FREE = ' ';
	final static char C_WALKED = '+';
	final static char C_START = 's';
	final static char C_EXIT = 'e';

	final static char[][] LABYRINTH_1 = {
		{'X','s','X','X','X','X','X','X'},
		{'X',' ',' ',' ','X',' ',' ','X'},
		{'X','X','X',' ','X',' ','X','X'},
		{'X',' ','X',' ',' ',' ',' ','X'},
		{'X',' ',' ',' ','X','X',' ','X'},
		{'X','X','X','X','X','X','e','X'} };

	final static char[][] LABYRINTH_2 = {
		{'X','s','X','X','X','X','X','X'},
		{'X',' ',' ',' ','X',' ',' ','X'},
		{'X','X','X',' ','X',' ','X','X'},
		{'X',' ','X',' ',' ',' ',' ','X'},
		{'X',' ',' ',' ','X','X','X','X'},
		{'X','X','X','X','X','X','e','X'} };

	private boolean step(char[][] lab, int x, int y) {

		System.out.println(toString(lab));

		if (lab[x][y] == C_WALL || lab[x][y] == C_WALKED) {
			/* Wand oder schon mal dort gewesen */
			return false;

		} else if (lab[x][y] == C_EXIT) {
			/* Ausgang -> terminieren */
			return true;

		} else if (lab[x][y] == C_FREE || lab[x][y] == C_START) {
			/* Feld markieren */
			lab[x][y] = C_WALKED;

			/* nach links */
			if (y > 0) {
				if (step(lab, x, y-1))
					return true;
			}

			/* nach unten */
			if (x < lab.length-1) {
				if (step(lab, x+1, y))
					return true;
			}

			/* nach rechts */
			if (y < lab[x].length-1) {
				if (step(lab, x, y+1))
					return true;
			}

			/* nach oben */
			if (x > 0) {
				if (step(lab, x-1, y))
					return true;
			}

			/* ging alles nicht -> Schritt zurueck gehen */
			lab[x][y] = C_FREE;
			return false;

		} else {
			/* unbekannter Eintrag */
			System.err.println("Unbekannter Eintrag");
			return false;
		}
	}

	public boolean solve(char[][] lab) {
		/* Start der Einfachkeit halber immer auf (0,1) */
		return step(lab, 0, 1);
	}

	public String toString(char[][] lab) {
		String s = "";
		for(int l=0; l < lab.length; l++) {
			for(int c=0; c < lab[l].length; c++) {
				s += lab[l][c];
			}
			s += "\n";
		}
		return s;
	}

	public static void main(String[] args) {
		Labyrinth l = new Labyrinth();
		if (l.solve(LABYRINTH_1))
			System.out.println("Loesbar! :-)");
		else
			System.out.println("Nicht loesbar. :-(");
		System.out.println("\n-----------------------------\n");
		if (l.solve(LABYRINTH_2))
			System.out.println("Loesbar! :-)");
		else
			System.out.println("Nicht loesbar. :-(");
	}

}