There is a algorithm for walking through a maze that guarantees finding the exit. If there is not an exit, youll 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 youll arrive at the exit of the maze. Write recursive function mazeTraverse to walk through 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,

// 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 )

{

// Complete this function

} // 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 << ' ';

} // end for

cout << " Hit return to see next move ";

cin.get();

} // end function printMaze