Do you blow how to find your way through a maze? After you write this program, you will never be lost again!

Assume that a maze is a rectangular array of squares, some of which are blocked to represent wails. The maze has one entrance and one exit. For example, if xs represent the walls, a maze could appear as:

xxxxxxxxxxxxxxxxxx x x x xxxx x X XXXXX XXXXX XX X X XXXXX XXXXXXX XX X XX XX XX X X XXXXXXXXXX XX X xxxxxxxxxxxxoxxxxxxx

A creature, indicated in the previous diagram by o, sits just inside the maze at the entrance. Assume that the creature can move in only four directions: north, south, east, and west. In the diagram, north is up, south is down, east is to the right, and west is to the left. The problem is to move the creature through the maze from the entrance to the exit, if possible. As the creature moves, it should mark its path. At the conclusion of the trip through the maze, you should see both the correct path and incorrect attempts.

Squares in the maze have one of several states: CLEAR (the square is clear), WALL (die square is blocked and represents part of the wall), PATH (die square lies on the path to the exit), and VISITED (die square was visited, but going that way led to an impasse).

This problem uses two ADTs that must interact. The ADT creature represents the creatures current position and contains operations tiiat move the creature. The creature should be able to move north, south, east, and west one square at a time. It should also be able to report its position and mark its trail.

The ADT maze represents the maze itself, which is a two-dimensional rectangular arrangement of squares. Suppose diat we number the rows of squares from the top beginning with zero, and we number the columns of squares from the left beginning with zero. Thus, you can use a row number and a column number to identify uniquely any square within the maze. The ADT clearly needs a data structure to represent the maze. It also needs such data as the height and width of the maze, given in numbers of squares; the length of a side of a square; and the row and column coordinates of both the entrance to and the exit from the maze.

The ADT maze should also contain, for example, operations that create a specific maze, given a text file of data; display a maze; determine whether a particular square is part of the wall; determine whether a particular square is part of the path; and so on.

The text file that you will use to represent a maze is simple. An example of how this can be done for the previously given maze is:

20 7 width and height of maze in squares

0 18 row and column coordinate of maze exit

6 12 row and column coordinate of maze entrance

xxxxxxxxxxxxxxxxxx x x x xxxx x X XXXXX XXXXX XX X X XXXXX XXXXXXX XX X

X XXXXXXXXXX XX X

xxxxxxxxxxxx xxxxxxx

Each line in the file corresponds to a row in the maze; each character in a line corresponds to a column in the maze. Xs indicate blocked squares (the walls), and blanks indicate clear squares. This notation is convenient because you can see what the maze looks like as you design it.

If you are at the mazes entrance, you can systematically find your way out of the maze by using the following search algorithm. It involves backtracking that is, retracing your steps when you reach an impasse.

1. First, check whether you are at the exit. If you are, youre done (a very simple maze); if you are not, go to Step 2.

2. Try to move to tire square directly to the north by calling the methodgoNorth(described later). 3. IfgoNorth was successful, you are done. If it was unsuccessful, try to move to the square

directly to the west by calling the methodgoWest (described later). 4. IfgoWest was successful, you are done. If it was unsuccessful, try to move to the square

directly to the south by calling the methodgoSouth (described later). 5. IfgoSouth was successful, you are done. If it was unsuccessful, try to move to the square

directly to the east by calling the methodgoEast (described later). 6. IfgoEast was successful, you are done. If it was unsuccessful, you are still done, because no

path exists from the entrance to the exit.

The methodgoNorth will examine all the paths that start at the squaie to the north of the present square as follows. If the square directly to the north is clear, is inside the maze, and has not been visited before, move into diis square and mark it as part of the padi. (Note that you are moving from the soudi.) Check whether you are at the exit. If you are, youre done. Otherwise, try to find a path to the exit from here by trying all paths leaving this square except the one going south (going south would put you back in the square from which you just came) as follows. CallgoNorth\ if it is not successful, callgoWest and, if it is not successful, callgoEast. ItgoEast is not successful, mark this square as visited, move back into the square to the south, and return.

The following pseudocode describes thegoNorth algorithm:goNorth(maze, creature) if (the square to the north is clear, inside the maze, and unvisited) { Move to the north Mark the square as part of the path if (at exit) {success = true

} else { success =goNorth(maze, creature) if (!success) { success = goWest(maze, creature) if (success) { success =goEast(maze, creature) if (i success) { Mark square visited Backtrack south} //end if> //end if} //end if> //end if } else { success =false } //end if return success

Thegowest method will examine all the paths drat start at the square to the westot the present square as follows. If the square direcdy to the west is clear, is inside the maze, and has not been visited before, move into this square and mark it as part of the path. (Note that you are moving from the east.) Check whether you are at the exit. If you are, youre done. Otherwise, try to find a padi to the exit from here by trying all paths leaving this square except the one going east (diis would put you back in the square from which you just came) as follows. Call goNorth; if it is not successful, callgoWest and, if it is not successful, callgoSouth. IfgoSouth is not successful, mark this square as visited, move back into the square to the east, and return.

The methodsgoEast andgoSouth are analogous to the mediods just described.