Java Reference
In-Depth Information
Fig. 18.21
|
Sample outputs for Exercise 18.19.
18.20
(Maze Traversal Using Recursive Backtracking)
The grid of
#
s and dots (
.
) in Fig. 18.22 is
a two-dimensional array representation of a maze. The
#
s represent the walls of the maze, and the
dots represent locations in the possible paths through the maze. A move can be made only to a lo-
cation in the array that contains a dot.
# # # # # # # # # # # #
# . . . # . . . . . . #
. . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
Fig. 18.22
|
Two-dimensional array representation of a maze.
Write a recursive method (
mazeTraversal
) to walk through mazes like the one in Fig. 18.22.
The method should receive as arguments a 12-by-12 character array representing the maze and the
current location in the maze (the first time this method is called, the current location should be the
entry point of the maze). As
mazeTraversal
attempts to locate the exit, it should place the charac-
ter
x
in each square in the path. There's a simple algorithm for walking through a maze that guar-
antees finding the exit (assuming there's an exit). If there's no exit, you'll arrive at the starting
location again. The algorithm is as follows: From the current location in the maze, try to move one
space in any of the possible directions (down, right, up or left). If it's possible to move in at least
one direction, call
mazeTraversal
recursively, passing the new spot on the maze as the current spot.
