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

 */
public class MazeRunner {
   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

	traverseMaze(m.start());
	System.exit(0);
    }
   
   public static void traverseMaze(Position square)
   {
	// a linear structure to manage search
	ArrayList todo = new ArrayList();

	// begin by priming the arraylist with starting position
	todo.add(square);
	while (!todo.isEmpty())	// while we haven't finished exploring
	{
	    // take the top position from the stack and check for finish
	    square = (Position)todo.remove(todo.size() -1);
	    if (m.isVisited(square)) continue; // been here before
	    if (square.equals(goal)) {
		System.out.println(m); // print solution
		return;
	    }
	    // not finished.
	    // visit this location, and add neighbors to pool
	    m.visit(square);
	    if (m.isClear(square.north())) todo.add(square.north());
	    if (m.isClear(square.west())) todo.add(square.west());
	    if (m.isClear(square.south())) todo.add(square.south());
	    if (m.isClear(square.east())) todo.add(square.east());
	}
    }
    
}