import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
* 
* @author geoffreytowell
* Holds and solves a maze
*/
public class Maze
{
	/** The starting point */
	public static final char START  = 's';
	/** The exit */
	public static final char FINISH = 'e';
	/** A wall you cant go through walls */
	public static final char WWALL  = '|';
	/** A floor, you cant go through floors either */
	public static final char FLOOR  = '=';
	/** A pathway  */
	public static final char PATH   = ' ';
	/** A pathway that leads to the solution */
	public static final char SUCCESS_PATH = 'A';
	/** A pathway that was tried and then backtracked  */
	public static final char FAIL_PATH = 'z';
	
	/**
	* The internal representation of the maze
	* A 2d array of char
	*/
	char[][] mazeRep;
	
	/** 
	 * The legal move directions. In this case
	 * up down, right and left. One space only.
	 */
	Coordinate[] moves = { new Coordinate(1, 0), new Coordinate(0, 1), 
		new Coordinate(0, -1), new Coordinate(-1, 0) };
		
		/**
		* Maze constructor.  This takes the name of a file containing a maze and reads it into 
		* the internal represenation.
		* @param fileName the name of the file containing the maze
		* @throws FileNotFoundException
		* @throws ImproperMazeException
		* @throws IOException
		*/
		public Maze(String fileName) throws IOException, FileNotFoundException, ImproperMazeException
		{
			// first read the file into an array list to get the dimensions of the maze
			ArrayList<String> tmaz = new ArrayList<>();
			int wid=-1;
			try (BufferedReader br = new BufferedReader(new FileReader(fileName)); ) {
			String lin;
			while ((lin=br.readLine())!=null)
			{
				if (wid>0 && lin.length()!=wid)
				{
					throw new ImproperMazeException("Maze must be a rectangle current width="+wid+" new line width="+lin.length());
				}
				if (wid<0)
					wid=lin.length();
				tmaz.add(lin);
			}
			} catch (FileNotFoundException fnf) {
				throw fnf;
			} catch (IOException ioe) {
				throw ioe;
			}
			
			// with the file read complete, fill in the internal representation
			mazeRep = new char[tmaz.size()][wid];
			for (int i=0; i<tmaz.size(); i++)
			{
				String s = tmaz.get(i);
				for (int j=0; j<s.length(); j++)
				{
					if (s.charAt(j)==WWALL ||
					s.charAt(j)==FLOOR ||
					s.charAt(j)==START ||
					s.charAt(j)==FINISH ||
					s.charAt(j)==PATH)
					{
						mazeRep[i][j] = s.charAt(j);
					}
					else
					{
						throw new ImproperMazeException("Maze contains an unknown character ||" + s.charAt(j) + "||");
					}
				}
			}
		}
		
		/**
		* @return a string showing the maze
		*/
		@Override
		public String toString()
		{
			StringBuilder sb = new StringBuilder();
			for (int i=0; i<mazeRep.length; i++)
			{
				for (int j=0; j<mazeRep[i].length; j++)
				{
					sb.append(mazeRep[i][j]);
				}
				sb.append("\n");
			}
			return sb.toString();
		}
		
		/**
		* Set a character in the maze 
		* @param c the character to set into the maze
		* @param val the coordinate in which to set the character
		*/
		public void setCoordValue(Coordinate c, char val)
		{
			mazeRep[c.getD1()][c.getD2()]=val;
		}
		
		/**
		 * Actually do the work of searching for a solution
		 * @param c the start8ng coordinate
		 * @param depth the depth of the maze solving stack
		 * @return true is the maze can be solved.
		 */
		private boolean solve(Coordinate c, int depth)
		{
			String indt = "";
			for (int i=0; i<depth; i++)
			indt += "  ";
			//System.out.println(indt +"Considering " + c);
			// make sure we are still inside the maze.  If not then return false
			if (c.getD1()<0 || 
			c.getD2()<0 || 
			c.getD1() >= mazeRep.length ||
			c.getD2() >= mazeRep[c.getD1()].length)
			{
				//System.out.println(indt+"   Off Grid");
				return false;
			}
			// are we at the solution?
			if (mazeRep[c.getD1()][c.getD2()]==FINISH)
			{
				setCoordValue(c, SUCCESS_PATH);
				System.out.println(indt+"   Solved");
				return true;
			}
			// Are we at a floor or wall?
			if (mazeRep[c.getD1()][c.getD2()]==WWALL || mazeRep[c.getD1()][c.getD2()]==FLOOR)
			{
				//System.out.println(indt+"   Wall");
				return false;
			}
			// have we been here before (via some other path)
			if (mazeRep[c.getD1()][c.getD2()]==FAIL_PATH)
			{
				//System.out.println(indt+"   Been here");
				return false;
			}
			// We are at a valid path (we must be because we have checked for everything else)
			if (mazeRep[c.getD1()][c.getD2()]==PATH)
			{
				setCoordValue(c, SUCCESS_PATH);
				// Since we just moved, let make another move
				// try each of the possible moves unless one works.
				for (Coordinate mv : moves)
				{
					if (solve(new Coordinate(c, mv), depth+1))
						return true;
				}
				// no path worked. so backtrack.  Before doing do, put down a breadcrumb saying 
				// I have been here.
				setCoordValue(c, FAIL_PATH);
			}
			//System.out.println(indt+"   No way forward");
			// only get here if have tried everythign and failed
			return false;	
		}
		
		/**
		* Find the location of the starting point
		* @return the location of the starting point (or null if there is no start)
		*/
		public Coordinate getStart()
		{
			for (int i=0; i<mazeRep.length; i++)
			for (int j=0; j<mazeRep[i].length; j++)
			if (mazeRep[i][j]==START)
			return new Coordinate(i, j);
			return null;
		}
		
		/**
		 * Try to solve this maze
		 * @return true if the maze is solvable
		 */
		public boolean solve()
		{
			Coordinate mstart = getStart(); // find the starting point of the maze
			if (mstart!=null)
			{
				setCoordValue(mstart, PATH); // replace the start indicator
				return solve(mstart, 0);
			}
			else
			{
				System.out.println("No starting point");
				return false;
			}
			
		}
		public static void main(String[] args)
		{
			String filename;
			try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
				System.out.print("Name of maze file: ");
				filename = br.readLine();
			} catch (IOException ioe) {
				System.err.println("Problem reading from keyboard -- giving up");
				return;
			}
			Maze m;
			try
			{
				m = new Maze(filename);
			}
			catch (FileNotFoundException fnf)
			{
				System.err.println(fnf + " " + filename); 
				return;
			}
			catch (ImproperMazeException ime)
			{
				System.err.println(ime);
				return;
			}
			catch (IOException ioe) {
				System.err.println(ioe);
				return;
			}
			if (m.solve())
			{
				System.out.println(m);
			}
			else
				System.out.println(m);
		}
		
		
	}