Write recursive function mazeTraverse to walk through the maze. The function should receive arguments that include a 12-by-12 character array representing the maze and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character X in each square in the path. The function should display the maze after each move, so the user can watch

Question

as the maze is solved.

(Maze Traversal) The grid of hashes (#) and dots (.) in Fig. 7.22 is a two-dimensional array representation of a maze. In the two-dimensional array, the hashes represent the walls of the maze and the dots represent squares in the possible paths through the maze. Moves can be made only to a location in the array that contains a dot.


There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming that there is an exit). If there is not an exit, you’ll arrive at the starting location again. Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you’ll arrive at the exit of the maze. There may
be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm.

Answer 1

```
// This solution assumes that there is only one
// entrance and one exit for a given maze, and
// these are the only two dots on the borders.
#include
using namespace std;

enum Direction { DOWN, RIGHT, UP, LEFT };

// function prototypes
void mazeTraversal( char [][ 12 ], const int, const int, int, int, int );
void printMaze( const char[][ 12 ] );
bool validMove( const char [][ 12 ], int, int );
bool coordsAreEdge( int, int );

int main()
{
char maze[ 12 ][ 12 ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
{'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
{'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };

int xStart = 2; // starting X and Y coordinates for maze
int yStart = 0;
int x = xStart; // current X and Y coordinates
int y = yStart;

mazeTraversal( maze, xStart, yStart, x, y, RIGHT );
} // end main

// Assume that there is exactly 1 entrance and exactly 1 exit to the maze.
void mazeTraversal( char maze[][ 12 ], const int xStart, const int yStart,
int xCoord, int yCoord, int direction )
{
static bool flag = false;

maze[ xCoord ][ yCoord ] = 'x';
printMaze( maze );

if ( coordsAreEdge( xCoord, yCoord ) && xCoord != xStart &&
yCoord != yStart )
{
cout << "\nMaze successfully exited!\n\n";
return; // maze is complete
} // end if
else if ( xCoord == xStart && yCoord == yStart && flag )
{
cout << "\nArrived back at the starting location.\n\n";
return;
} // end else if
else
{
flag = true;

// for loop uses switch to determine appropriate move
for ( int move = direction, count = 0; count < 4; count++,
move++, move %= 4 )
{
switch( move )
{
case DOWN: // move down
if ( validMove( maze, xCoord + 1, yCoord ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord + 1, yCoord, LEFT );
return;
} // end if
break;
case RIGHT: // move right
if ( validMove( maze, xCoord, yCoord + 1 ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord, yCoord + 1, DOWN );
return;
} // end if
break;
case UP: // move up
if ( validMove( maze, xCoord - 1, yCoord ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord - 1, yCoord, RIGHT );
return;
} // end if
break;
case LEFT: // move left
if ( validMove( maze, xCoord, yCoord - 1 ) )
{
mazeTraversal(
maze, xStart, yStart, xCoord, yCoord - 1, UP );
return;
} // end if
break;
} // end switch
} // end for
} // end else
} // end function mazeTraversal

// validate move
bool validMove( const char maze[][ 12 ], int r, int c )
{
return
( r >= 0 && r <= 11 && c >= 0 && c <= 11 && maze[ r ][ c ] != '#' );
} // end function validate

// function to check coordinates
bool coordsAreEdge( int x, int y )
{
if ( ( x == 0 || x == 11 ) && ( y >= 0 && y <= 11 ) )
return true;
else if ( ( y == 0 || y == 11 ) && ( x >= 0 && x <= 11 ) )
return true;
else
return false;
} // end function coordsAreEdge

// print the current state of the maze
void printMaze( const char maze[][ 12 ] )
{
// nested for loops to iterate through maze
for ( int x = 0; x < 12; x++ )
{
for ( int y = 0; y < 12; y++ )
cout << maze[ x ][ y ] << ' ';

cout << '\n';
} // end for

cout << "\nHit return to see next move\n";
cin.get();
} // end function printMaze
```
# # # # # # # # # # # #
# . . . # . . . . . . #
x . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
Hit return to see next move
.
.
.

# # # # # # # # # # # #
# x x x # x x x x x x #
x x # x # x # # # # x #
# # # x # x x x x # x #
# x x x x # # # x # x x
# # # # x # . # x # x #
# x x # x # . # x # x #
# # x # x # . # x # x #
# x x x x x x x x # x #
# # # # # # x # # # x #
# x x x x x x # x x x #
# # # # # # # # # # # #
Hit return to see next move
Maze successfully exited!