/*
  An example of the use of recursion. The 'findExit' algorithm comes from
  "An Introduction to Computer Science Using Java" by John Carter.
*/


public class Maze
{
    private char [][] world = {
	                       {'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W'},
                               {'W', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', ' ', 'W', 'W', 'W'},
                               {'W', ' ', 'W', 'W', 'W', ' ', ' ', ' ', 'W', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', ' ', 'W', 'W', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', ' ', ' ', ' ', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', 'W', 'W', ' ', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', 'W', 'W', ' ', 'W'},
                               {'W', ' ', 'W', 'W', 'W', 'W', 'W', 'W', ' ', 'W'},
                               {'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'X', 'W'},
                              };
    public final int ROWS = 10;
    public final int COLUMNS = 10;
    public final char EMPTY = ' ';
    public final char WALL = 'W';
    public final char EXIT = 'X';
    public final char GOOD_PATH = '+';
    public final char TRIED = '-';    


    public void display ()
    {
	int r;
	for(r = 0; r < ROWS; r++)
	{
	    System.out.println(world[r]);
	}
	System.out.println();
    }

    public boolean findExit (int r, int c)
    {
	boolean done = false;
	if (world[r][c] == EXIT)
	{
	    world[r][c] = GOOD_PATH;
	    done = true;
	}
	else
	{
	    world[r][c] = TRIED;
	    // TRY NORTH
	    if ((world[r-1][c] == EMPTY) || (world[r-1][c] == EXIT))
		done = findExit (r-1,c);
	    if (!done)
	    {
		// TRY WEST
		if ((world[r][c-1] == EMPTY) || (world[r][c-1] == EXIT))
		    done = findExit (r,c-1);
	    }
	    if (!done)
	    {
		// TRY EAST
		if ((world[r][c+1] == EMPTY) || (world[r][c+1] == EXIT))
		    done = findExit (r,c+1);
	    }
	    if (!done)
	    {
		// TRY SOUTH
		if ((world[r+1][c] == EMPTY) || (world[r+1][c] == EXIT))
		    done = findExit (r+1,c);
	    }
	    // Checked 4 directions, one direction had exit then mark this as part of good path
	    if (done)
		world[r][c] = GOOD_PATH;
	}
	return done;
    }

    public void start ()
    {
	boolean found;
	display();
	// Starting (row/col) position in the maze is passed as a parameter.
	found = findExit (1,1);
	if (found)
	    System.out.println("Exit was found!\n");
	else
	    System.out.println("There's no exit from the maze.\n");
	display();
    }
}


class Driver
{
    public static void main (String args [])
    {
	Maze aMaze = new Maze ();
        aMaze.start ();
    }
}