cmsc433.p3
Class STMazeSolverDFS

java.lang.Object
  cmsc433.p3.MazeSolver
      cmsc433.p3.SkippingMazeSolver
          cmsc433.p3.STMazeSolverDFS

public class STMazeSolverDFS
extends SkippingMazeSolver

An efficient single-threaded depth-first solver.

Nested Class Summary

Nested classes/interfaces inherited from class cmsc433.p3.SkippingMazeSolver

SkippingMazeSolver.SolutionFound

Constructor Summary

STMazeSolverDFS(Maze maze)

Method Summary

java.util.List<Direction>

solve() Performs a depth-first search for the exit.

Methods inherited from class cmsc433.p3.SkippingMazeSolver

firstChoice, follow, followMark, markPath, pathToFullPath

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

STMazeSolverDFS

public STMazeSolverDFS(Maze maze)

Method Detail

solve

public java.util.List<Direction> solve()

Performs a depth-first search for the exit. The solver operates by maintaining a stack of choices. During each iteration, the choice at the top of the stack is examined. If choice.isEmpty() is true, then we have reached a dead-end and must backtrack by popping the stack. If the choice is not empty, then we proceed down the first path in the list of options. If the exit is encountered, then SolutionFound is thrown and we generate the solution path, which we return. At any given point in the execution, the list of first choices yields the current path. That is, if the choice stack is:

[[E W S] [E W] [S N] [N]]

Then the current path is given by the list:

[E E S N]

Specified by:

solve in class MazeSolver

Returns:

The list of directions that would lead a person from the maze start to the end.