import java.util.*;
/*
Input                         Output
10
####################          ####################
#s#       #f   #   #          #s#       #f...#...#
# ####### #### # # #          #.####### ####.#.#.#
#         #  # ### #          #.........#..#.###.#
##### ### #        #          ##### ###.#........#
#   # #   ####### ##          #   # #...#######.##
#   # # ### #   #  #          #   # #.### #...#..#
#   # # #   # # ## #          #   # #.#...#.#.##.#
#     #   #   #    #          #     #...#...#....#
####################          ####################

 */
public class MazeRunnerRecursiveV3 {
   static Maze m;
   static Position goal;
    public static void main(String[] arguments)
    {

	m = new Maze("MazeRunner.input"); // the maze	

	goal = m.finish(); // where the finish is
	boolean done = traverseMaze(m.start());
    }
   
   public static boolean traverseMaze(Position p)
   {
      boolean found = false;
	if (!m.isVisited(p))
	    if (p.equals(goal)) {
		System.out.println(m); // print solution
		found = true;}
		// return found;}
	    else {
	    // visit this location, and its neighbors 
	    m.visit(p);
	    ListIterator surround = m.neighbors(p);
	    while (!found && surround.hasNext())
	    {
		found = traverseMaze((Position)surround.next());
	    }

	    // The repetitive code below has been replaced by the
	    // iterator and use of it shown above

	    /* if (m.isClear(p.north()) && ! found ) found = traverseMaze(p.north());
	    if (m.isClear(p.west()) && ! found ) found = traverseMaze (p.west());	    
	    if (m.isClear(p.south()) && !found ) found = traverseMaze(p.south());	
	    if (m.isClear(p.east()) && !found ) found = traverseMaze(p.east());*/
    }
	return found;
}

}