// ADD ANY NEEDED IMPORTS HERE

public class MazeSolver {

  ///////////////////
  // INNER CLASSES //
  ///////////////////

  public static class Choice {
    final static int RIGHT = 1;
    final static int DOWN = 2;
    final static int LEFT = 3;
    final static int UP = 4;
    
    // ADD ANY ADDITIONAL CONSTANTS DESIRED HERE
    
    int direction;  // <-- LIMIT YOURSELF TO ONLY THIS INSTANCE VARIABLE FOR THIS INNER CLASS
    
    private Choice(int direction) {
      // ADD CODE HERE
    }

    public static Choice firstChoice() {
      // ADD CODE HERE
    }

    public Choice nextChoice() {
      // ADD CODE HERE
    }

    public boolean unconsideredChoicesExist() {
      // ADD CODE HERE
    }

    public String toString() {
      // ADD CODE HERE
    }
  }

  public static class StackOfChoices implements Iterable<Choice> {

    final int WALL = 1;
    final int EMPTY = 0;
    
    // ADD ANY ADDITIONAL CONSTANTS DESIRED HERE

    private Stack<Choice> choices;  // <-- LIMIT YOURSELF TO ONLY THESE 3 INSTANCE VARIABLES FOR THIS INNER CLASS
    private int[][] maze;           //
    private boolean[][] visited;    //
    
    // YOU MAY FIND THE NEXT METHOD HELPFUL:
    
    private int[][] copyOf(int[][] a) {
      int[][] b = new int[a.length][a[0].length];

      for (int r = 0; r < a.length; r++) {
        for (int c = 0; c < a[0].length; c++) {
          b[r][c] = a[r][c];
        }
      }
      
      return b;
    }
    
    // HAVING AND USING THE NEXT 2 METHODS WILL HELP
    // SIMPLIFY YOUR CODE. FLESH THEM OUT SO THEY BEHAVE
    // AS DESCRIBED:
    
    private int endingRow() {
      // ADD CODE HERE TO RETURN THE ROW INDEX OF
      // WHERE ONE ENDS UP IF ONE STARTS AT ROW=0 COL=1
      // AND MAKES THE CHOICES IN THIS STACK OF CHOICES
      // IN THE ORDER THEY WERE ADDED TO THE STACK
    }
    
    private int endingCol() {
      // ADD CODE HERE TO RETURN THE COLUMN INDEX OF
      // WHERE ONE ENDS UP IF ONE STARTS AT ROW=0 COL=1
      // AND MAKES THE CHOICES IN THIS STACK OF CHOICES
      // IN THE ORDER THEY WERE ADDED TO THE STACK
    }

    public StackOfChoices(int[][] maze) {
      // ADD CODE HERE
    }

    public boolean isEmpty() {
      // ADD CODE HERE
    }

    public int size() {
      // ADD CODE HERE
    }

    public void push(Choice choice) {
      // ADD CODE HERE
    }

    public Choice peek() {
      // ADD CODE HERE
    }

    public Choice pop() {
      // ADD CODE HERE
    }
    
    public Iterator<Choice> iterator() {
      // ADD CODE HERE
    }

    public boolean isSolution() {
      // ADD CODE HERE
    }

    public boolean mightHaveSolutionWith(Choice c) {
      // ADD CODE HERE
    }

    // DO NOT MODIFY ANY OF THE CODE FROM THIS POINT DOWN.
    // THAT SAID, MAKE SURE YOU LOOK AT IT CAREFULLY AND UNDERSTAND IT.
    // THAT KNOWLEDGE WILL HELP YOU AS YOU FLESH OUT THE INCOMPLETE METHODS ABOVE
    
    public String toString() {
      final String WALL_STR = "\u2591";      // i.e., the unicode character for a lightly-shaded block
      final String EMPTY_STR = " ";
      final String VISITED_STR = "\u2022";   // i.e., the unicode character for a small dot
      final String START_STR = "S";
      final String FINISH_STR = "F";
      
      String[][] mazeToShow = new String[this.maze.length][this.maze[0].length];
      
      int row,col;
      
      // fill mazeToShow with strings for walls and (initially) empty corridors
      for (row = 0; row < this.maze.length; row++) 
        for (col = 0; col < this.maze[0].length; col++) 
          mazeToShow[row][col] = (this.maze[row][col] == WALL ? WALL_STR : EMPTY_STR);
      
      // add strings for any corridors visited by making the choices made so far
      row = 0;
      col = 1; // start of maze is required to be at this row/col position
      
      for (Choice choice : choices) {
        switch (choice.direction) {
        case Choice.RIGHT : col++; break;
        case Choice.DOWN  : row++; break;
        case Choice.LEFT  : col--; break;
        case Choice.UP    : row--; break;
        }
        mazeToShow[row][col] = VISITED_STR;
      }
      
      // add strings for start and finish
      mazeToShow[0][1] = START_STR;
      mazeToShow[this.maze.length-1][this.maze[0].length-2] = FINISH_STR;
      

      // convert the array of strings to a single printable string s
      String s = "";
      for (row = 0; row < this.maze.length; row++) {
        for (col = 0; col < this.maze[0].length; col++) {
          s += mazeToShow[row][col];
        }
        s += "\n";
      }

      return s;
    }
  }

  private StackOfChoices stackOfChoicesMade;   
  private Stack<String> stackOfSolutions;

  public MazeSolver(int[][] grid) {
    stackOfChoicesMade = new StackOfChoices(grid);
    stackOfSolutions = new Stack<String>();
  }

  public boolean solutionFound() {
    return (stackOfChoicesMade.isSolution());
  }

  public void solve() throws InterruptedException { // THIS METHOD USES THE BACKTRACKING ALGORITHM (WITH A STACK)

    Choice choice = Choice.firstChoice();

    while (true) {

      if (stackOfChoicesMade.mightHaveSolutionWith(choice)) {
        stackOfChoicesMade.push(choice);
        //System.out.println(stackOfChoicesMade); // <-- uncomment this line to see the choices made so far 
        choice = Choice.firstChoice();
      } else if (choice.unconsideredChoicesExist()) {
        choice = choice.nextChoice();
      } else {
        if (stackOfChoicesMade.isEmpty()) // Here, you intend to pop to backtrack if you can.
          break; // If you can't (because the stack is empty), you are done!

        choice = stackOfChoicesMade.pop().nextChoice(); // If the pop is safe, pick up where you
                                // left off with your last choice.
                                // (i.e., choose the next choice after that one)
      }

      if (solutionFound()) {
        reactToSolutionFound();
        choice = stackOfChoicesMade.pop(); // normally we check to make sure -- but it's safe to pop.. why?
        choice = choice.nextChoice(); // keep going to try to find other solutions
      }
    }
  }

  public void reactToSolutionFound() {
    stackOfSolutions.push(stackOfChoicesMade.toString());
  }
  
  public static void solveMaze(int[][] maze) throws InterruptedException {
    MazeSolver solver = new MazeSolver(maze);
    System.out.println("NEW MAZE:\n\n" + solver.stackOfChoicesMade);
    solver.solve();
    System.out.println(solver.stackOfSolutions.size() + " solutions(s) found:\n");
    for ( String solution : solver.stackOfSolutions) {
        System.out.println(solution);
    }
  }

  public static void main(String[] args) throws InterruptedException {

    int[][] solvableMaze =  {{1,0,1,1,1,1,1,1,1,1,1},
                             {1,0,1,0,0,1,1,0,0,0,1},
                             {1,0,1,1,0,1,0,0,1,0,1},
                             {1,0,1,0,0,0,0,1,1,0,1},
                             {1,0,0,0,1,1,0,1,0,0,1},
                             {1,1,1,0,1,0,0,1,0,1,1},
                             {1,0,0,0,1,1,0,1,0,0,1},
                             {1,0,1,0,1,0,0,0,1,0,1},
                             {1,1,1,1,1,1,1,1,1,0,1}};
    
    solveMaze(solvableMaze);
    
    int[][] multipleSolutionMaze = {{1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                                    {1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
                                    {1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1},
                                    {1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1},
                                    {1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1},
                                    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1},
                                    {1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
                                    {1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
                                    {1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
                                    {1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1},
                                    {1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1},
                                    {1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
                                    {1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1},
                                    {1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1},
                                    {1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1},
                                    {1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1},
                                    {1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1},
                                    {1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
                                    {1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1},
                                    {1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
                                    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
    
    solveMaze(multipleSolutionMaze);
    
    int[][] unsolvableMaze = {{1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
                              {1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1},
                              {1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1},
                              {1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1},
                              {1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1},
                              {1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1},
                              {1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
                              {1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
                              {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
                              {1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
                              {1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1},
                              {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
                              {1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1},
                              {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1},
                              {1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
                              {1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1},
                              {1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1},
                              {1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1},
                              {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1},
                              {1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1},
                              {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
    
    solveMaze(unsolvableMaze);
  }
}