MazeSolver.java.html

  1  import java.util.Stack;
  2  
  3  /**
  4     This program uses a stack to find a path from a position 
  5     in a maze to an exit. It is assumed that the maze has no circular
  6     paths, and that there is at least one exit.
  7  */
  8  public class MazeSolver
  9  {
 10     public static void main(String[] args)
 11     {
 12        Maze maze = new Maze(
 13           new String[] {
 14              "*****************************",
 15              "** ***                      *",
 16              "** *** * ********************",
 17              "** *** *         *          *",
 18              "** *** * *******   **** *****",
 19              "**     * ************** *****",
 20              "****** ******* *******  *****",
 21              "******         ******* ******",
 22              "*      ******* ******* ******",
 23              "* **** ******* **           *",
 24              "*    ********* ******* ******",
 25              "* ****         ***     ******",
 26              "************** **************"});
 27  
 28        solve(maze, 5, 8);
 29     }
 30  
 31     /**
 32        Traverses a maze, printing out a path to the exit.
 33        @param maze the maze
 34        @param param the row of the starting position
 35        @param param the column of the starting position
 36     */
 37     public static void solve(Maze maze, int row, int column)
 38     {
 39        Stack<Path> s = new Stack<Path>();
 40        for (Path p : maze.pathsFrom(row, column))
 41        {
 42           s.push(p);
 43        }
 44  
 45        while (s.size() > 0)
 46        {
 47           Path p = s.pop();
 48           System.out.println("Following " + p);
 49           int r = p.getEndingRow();
 50           int c = p.getEndingColumn();
 51           if (maze.isExit(r, c))
 52           {
 53              System.out.println("Exit!");
 54              return;
 55           }
 56           else if (maze.isDeadEnd(r, c))
 57           {
 58              System.out.println("Dead end");
 59           }
 60           else 
 61           {
 62              for (Path p2 : maze.pathsFrom(r, c))
 63              {
 64                 if (!p2.isOpposite(p))
 65                 {                  
 66                    s.push(p2);
 67                 }
 68              }
 69           }
 70        }
 71     }
 72  }