package smalldemo.maze;

 class MazeCell {

  public int x,y;

  public MazeCell(){

  }

  public MazeCell(int x,int y){

      this.x=x;

      this.y=y;

  }

  public boolean equals(MazeCell cell){

     return x==cell.x && y==cell.y;

  }

}

package smalldemo.maze;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintStream;

import java.util.Stack;

class MazeUtils {

    private int rows,columns;

    private MazeCell currentCell,exitCell=new MazeCell(),entryCell=new MazeCell();

    private final char wall='1',passage='0',visited='*',entryMarker='m',exitMarker='e';

    private char[][] stores;

    private Stack<MazeCell> mazePath=new Stack<MazeCell>();

    MazeUtils(){

        int row=0,column=0;

        InputStreamReader in=new InputStreamReader(System.in);

        BufferedReader buf=new BufferedReader(in);

        Stack<String> mazeRows=new Stack<String>();

        System.out.println("Enter a rectangular maze using the following"+

        "characters\nm -entry\ne -exit\n1 - wall \n0 - passage\n"+"Enter one line at one time:" +

                "end with Ctrl- D:");

        try {

            String str=buf.readLine();

            while(str !=null) {

                row += 1;

                columns = str.length();

                str = "1" + str + "1";

                mazeRows.push(str);

                if (str.indexOf(entryMarker) != -1) {

                    entryCell.x = row;

                    entryCell.y = str.indexOf(entryMarker);

                }

                if (str.indexOf(exitMarker) != -1) {

                    exitCell.x = row;

                    exitCell.y = str.indexOf(exitMarker);

                }

                str = buf.readLine();

            }

        } catch (IOException e) {

            e.printStackTrace();

        }

        rows=row;

        stores=new char[rows+2][];

        stores[0]=new char[columns+2];

        for(;!mazeRows.empty();row --){

            stores[row]=mazeRows.pop().toCharArray();

        }

        stores[rows+1]=new char[columns+2];

        for(int i=0;i<columns+2;i+=1){

            stores[0][i]=wall;

            stores[rows+1][i]=wall;

        }

    }

    private void display(PrintStream out){

        for(int row =0;row <rows +1;row+=1){

            out.println(stores[row]);

        }

        out.println();

    }

    private void pushUnvisited(int row,int col){

        if(stores[row][col] ==passage || stores[row][col] == exitMarker){

            mazePath.push(new MazeCell(row,col));

        }

    }

    public void exitMaze(PrintStream out){

        currentCell=entryCell;

        out.println();

        while (!currentCell.equals(exitCell)){

            int x=currentCell.x;

            int y=currentCell.y;

            display(System.out);

            stores[x][y]=visited;

            pushUnvisited(x-1,y);

            pushUnvisited(x+1,y);

            pushUnvisited(x,y-1);

            pushUnvisited(x,y+1);

            if(mazePath.isEmpty()){

                display(out);

                out.println("Failure");

                return;

            }

            else{

                currentCell=mazePath.pop();

            }

        }

        display(out);

        out.println("Success!");

    }

    public static void main(String[] args){

        new MazeUtils().exitMaze(System.out);

    }

}