HW5: Mazes, Part II

1. Read in the maze description from a file.
2. Mark every square in the maze as unvisited.
3. Create an empty stack of maze squares.
4. Push the start square onto the stack, and mark the start square as visited.
5. If the stack is empty, you're done and the maze is unsolvable. Otherwise, let $T$ be the top item on the stack.
6. If $T$ is the finish square, you're done and the stack contains a solution to the maze.
7. If all squares adjacent to $T$ (i.e. the squares up, down, right, or left from T — no diagonal adjacency) are either blocked from $T$ by a wall or are marked visited already, pop $T$ off the stack and go to step 5.
8. Otherwise, select a square $S$ that is adjacent to $T$, unvisited, and accessible from $T$ (no wall between them). Mark $S$ as visited and push it on the stack. Go to step 5.

Supplement your Maze.java from the last assignment to support solving mazes and printing the solved version.

Specifically:

• Your Maze class must include a method with the following signature:

  /**
   * Computes and returns a solution to this maze. If there are multiple
   * solutions, only one is returned, and getSolution() makes no guarantees about
   * which one. However, the returned solution will not include visits to dead
   * ends or any backtracks, even if backtracking occurs during the solution
   * process.
   *
   * @return a stack of Square objects containing the sequence of squares
   * visited to go from the start square (bottom of the stack) to the finish
   * square (top of the stack).
   */
  private Stack<Square> getSolution()
  

• Your program's command line should follow the syntax:

  java Maze <mazeFile> [--solve]
  

  For example, suppose maze.txt contains:

  6 5
  0 0
  0 4
  L-_|_-
  |L--|_
  |-_-|_
  |L|L||
  L__L__
  

  then this command:

  java Maze maze.txt
  

  should print the maze with no solution, like so:

  +-----+-----+-----+-----+-----+-----+
  |                 |                 |
  |  S              |                 |
  |                 |                 |
  +-----+     +-----+     +-----+     +
  |     |                 |           |
  |     |                 |           |
  |     |                 |           |
  +     +-----+     +     +     +-----+
  |                       |           |
  |                       |           |
  |                       |           |
  +     +     +-----+     +     +-----+
  |     |     |     |     |     |     |
  |     |     |     |     |     |     |
  |     |     |     |     |     |     |
  +     +-----+     +-----+     +     +
  |                 |                 |
  |  F              |                 |
  |                 |                 |
  +-----+-----+-----+-----+-----+-----+
  

  However, this command:

  java Maze maze.txt --solve
  

  should print the maze with the path of a solution marked, like so:

  +-----+-----+-----+-----+-----+-----+
  |                 |                 |
  |  S     *        |                 |
  |                 |                 |
  +-----+     +-----+     +-----+     +
  |     |                 |           |
  |     |  *     *     *  |           |
  |     |                 |           |
  +     +-----+     +     +     +-----+
  |                       |           |
  |  *     *     *     *  |           |
  |                       |           |
  +     +     +-----+     +     +-----+
  |     |     |     |     |     |     |
  |  *  |     |     |     |     |     |
  |     |     |     |     |     |     |
  +     +-----+     +-----+     +     +
  |                 |                 |
  |  F              |                 |
  |                 |                 |
  +-----+-----+-----+-----+-----+-----+