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 }