import java.util.Arrays;

public class Maze {

    private MazeRunnerStack path;
    private MazeRunnerStack shortenPath;
    private Boolean solved;
    private static int WIDTH=4; //4
    private static int HEIGHT=3; //3
    private static char[][] mazeInfo = new char[WIDTH][HEIGHT];;
    private char[][] position ;//= new char[WIDTH][HEIGHT];
    private static int maxCount;

    public Maze(char[][] mazeInfo) {   //initalize width and height of the maze, set max count to the value width*height*4

        mazeInfo[0][0] = 'L';
        mazeInfo[0][1] = '.';
        mazeInfo[0][2] = '|';
        mazeInfo[1][0] = '|';
        mazeInfo[1][1] = '_';
        mazeInfo[1][2] = '.';
        mazeInfo[2][0] = '|';
        mazeInfo[2][1] = '|';
        mazeInfo[2][2] = '|';
        mazeInfo[3][0]= 'L';
        mazeInfo[3][1]='_';
        mazeInfo[3][2]='_';

        WIDTH = mazeInfo[0].length;
        HEIGHT = mazeInfo.length;

        this.solved = false;
        this.maxCount = WIDTH*HEIGHT* 4;position = new char[HEIGHT][WIDTH];
        for (int i = 0; i < mazeInfo.length; i++) {
            for (int j = 0; j < mazeInfo[i].length; j++) {
                position[i][j] = 'z';
            }
        }

        //System.out.print(maxCount);

    };

    public void setStart(int row, int col) {     //assign all the position to random letter to avoid null pointer exception. set start

        this.position[row][col] = 'S';
    };

//  public void setFinish(int row, int col) {
//      this.position[row][col] = 'F';
//  };

    public void setFinish(int row, int col)    //set the finish point for the maze
    {
        this.position[row][col] = 'F';
    };

    public void displayMaze(MazeRunnerStack path) {   //print out the maze

        if (true) { // change to !solved
            int count = 0;
            System.out.println("+---+---+---+");
            for (int i = 0; i < mazeInfo.length; i++) {
                int[] temp = new int[3];
                for (int j = 0; j < mazeInfo[i].length; j++) {
                    // System.out.print(j);
                    if (mazeInfo[i][j] == 'L' || mazeInfo[i][j] == '.' || mazeInfo[i][j] == '_'
                            || mazeInfo[i][j] == '|') {
                        char ch = mazeInfo[i][j];    //initialize



                        {

                            switch (ch) {      //check the wall type, print out depend on the wall

                            case 'L': // 1         //wall on the left side and botton


                                if (position[i][j] == 'S')
                                    System.out.print("| S ");
                                else if (position[i][j] == 'F')
                                    System.out.print("| F ");
                                else if(path.contains(new Position(i, j)) )
                                    System.out.print("| * ");
                                else
                                    System.out.print("|   ");
                                temp[j] = 1;
                                break;
                            case '.':// 2                  //no wall
                                if (position[i][j] == 'S')
                                    System.out.print("  S ");
                                else if (position[i][j] == 'F')
                                    System.out.print("  F ");
                                else if(path.contains(new Position(i, j)) )
                                    System.out.print("  * ");
                                else
                                    System.out.print("    ");
                                temp[j] = 2;
                                break;
                            case '|': // 3                 //wall on the left
                                if (position[i][j] == 'S')
                                    System.out.print("| S ");
                                else if (position[i][j] == 'F')
                                    System.out.print("| F ");
                                else if(path.contains(new Position(i, j)))
                                    System.out.print("| * ");
                                else
                                    System.out.print("|   ");
                                temp[j] = 3;
                                break;
                            case '_': // 4                //wall on the bottom
                                if (position[i][j] == 'S')
                                    System.out.print("  S ");
                                else if (position[i][j] == 'F')
                                    System.out.print("  F ");
                                else if(path.contains(new Position(i, j)))
                                    System.out.print("  * ");
                                else
                                    System.out.print("    ");
                                temp[j] = 4;
                                break;
                            }
                        }

                    }

                }
                if (count % 2 == 0) // the last char of each line , eitehr "+" or "|"
                    System.out.print("|");
                else if (count % 2 == 1)
                    System.out.print("+");
                System.out.println();

                for (int k = 0; k < temp.length; k++) {

                    if (temp[k] == 1 || temp[k] == 4)
                        System.out.print("+---");
                    else if (temp[k] == 2 || temp[k] == 3)
                        System.out.print("+   ");
                }
                if (count % 2 == 0) // the last char of the very next line
                    System.out.print("+");
                else if (count % 2 == 1)
                    System.out.print("|");
                System.out.println();

            }
            count++;
        }
    };

    public void solveMaze() {
        int attempts = 0;
        path = new MazeRunnerStack();
        shortenPath=new MazeRunnerStack();   //creating  a new path
        char direction = 'E'; // Can be N, E, S, W to represent North West East and South
        Position currPosition;
        for (int i = 0; i < position.length; i++) {         //push the starting point in the stack
            for (int j = 0; j < position[i].length; j++) {
                if (position[i][j] == 'S') {
                    currPosition = new Position(i, j);
                    path.push(currPosition);
                    break;
                }
                // path.push(item);
            }
        }

        while (!solved ) {                          //keep running until its solved
            Position topStack = path.peek();
            if(mazeInfo==null|mazeInfo.length==0)
                break;
            if(attempts>=maxCount)
                break;


            if (position[topStack.row][topStack.col] == 'F') {
                this.solved = true;
                break;
            }
            //System.out.println(topStack.row + ", " + topStack.col + "     dir: " + direction);
            switch (direction) {

            case 'w': // north
            case 'W':
                if (topStack.row - 1 < 0) {
                    direction = 's';
                } else if (mazeInfo[topStack.row - 1][topStack.col] == 'L'
                        || mazeInfo[topStack.row - 1][topStack.col] == '_')
                    direction = 's';//'e'
                else {
                    currPosition = new Position(topStack.row - 1, topStack.col);
                    path.push(currPosition);
                    direction='n';


                }
                attempts++;
                break;

            case 'n': // east
            case 'N':
                if (topStack.col + 1 >= WIDTH) {
                    direction = 'w';
                } else if (mazeInfo[topStack.row][topStack.col + 1] == 'L'
                        || mazeInfo[topStack.row][topStack.col + 1] == '|') {
                    direction = 'w';
                } else {
                    currPosition = new Position(topStack.row, topStack.col + 1);
                    path.push(currPosition);
                    // System.out.print(Arrays.toString(path.peek()));
                    direction='e';
                }
                attempts++;
                break;

            case 'e': // south
            case 'E':
                if (topStack.row + 1 >= HEIGHT) {
                    direction = 'n';
                } else if (mazeInfo[topStack.row][topStack.col] == 'L' || mazeInfo[topStack.row][topStack.col] == '_') {
                    direction = 'n';
                } else {
                    currPosition = new Position(topStack.row + 1, topStack.col);
                    path.push(currPosition);
                    direction='s';
                }
                attempts++;
                break;

            case 's': // west
            case 'S':
                if (topStack.col - 1 < 0) {
                    direction = 'e';
                } else if (mazeInfo[topStack.row][topStack.col] == 'L' || mazeInfo[topStack.row][topStack.col] == '|') {
                    direction = 'e';
                } else {
                    currPosition = new Position(topStack.row, topStack.col - 1);
                    path.push(currPosition);
                    direction='w';
                }
                attempts++;
                break;

            }


        }if(solved) {
            Position[] path1 = new Position[path.getSize()];
            for (int i = path1.length - 1; i >= 0; i--) { //pop all value ,assgin to path1
                path1[i] = path.pop();
            }
            for (int i = 0; i < path1.length; i++) {
                path.push(path1[i]);                       //restore the stack
            }
            System.out.println("Solution is:");
            for (int i = path1.length - 1; i >= 0; i--) {
                while (shortenPath.contains(path1[i])) {    //check whether contain,if contains, remove it until there is no same position
                    shortenPath.pop();
                }
                shortenPath.push(path1[i]);
            }

            displayMaze(shortenPath);                        //print out the maze
            Position[] newPath = new Position[shortenPath.getSize()];
            for (int i = 0; i < newPath.length; i++) {       //pop out the stack, assign the value to newPath
                newPath[i] = shortenPath.pop();
            }
            for (int i = newPath.length - 1; i >= 0; i--) {     //restore the stack again
                shortenPath.push(newPath[i]);
            }

            System.out.print("Path is: ");
            for (int i = 0; i < newPath.length; i++) {         //print out the path
                System.out.print("[" + newPath[i].row + "," + newPath[i].col + "]");
                if (i != newPath.length - 1)
                    System.out.print(" --> ");
            }
            System.out.println();
        }else {
            System.out.println("No Solution could be found.");
            displayMaze(shortenPath);
        }


    };

    public static void main(String[] args) {

        Maze test = new Maze(mazeInfo);
        test.setStart(0, 2);
        test.setFinish(2,1);
        test.solveMaze();



    }

}