Skip to content

Instantly share code, notes, and snippets.

@danvas

danvas/Ex08_25.cpp

Created November 17, 2011 04:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save danvas/1372358 to your computer and use it in GitHub Desktop.
Save danvas/1372358 to your computer and use it in GitHub Desktop.
Download ZIP
A maze!
Raw
Ex08_25.cpp
// Exercise 8.25 Solution: Ex08_25.cpp
// This solution assumes that there is only one
// entrance and at most one exit for a given maze, and
// these are the only two zeroes (at most) on the borders.
// NOTE: Your solution should work for all 3 test mazes below
#include <iostream>
using std::cin;
using std::cout;
enum Direction { DOWN, RIGHT, UP, LEFT };
const int SIZE = 12; //Assume the maze is always square
// function prototypes
// This function is invoked recursively in the solution provided by the text.
void mazeTraversal( char maze[][ SIZE ], const int & xStart, const int & yStart,
const int & xCoord, const int & yCoord, const Direction & dir );
// This function prints the maze
void printMaze( const char[][ SIZE ] );
//This function returns 'true' if the move is valid
bool validMove( const char maze[][ SIZE ], const int & row, const int & col );
//This function returns 'true' if we have exited the maze.
//NOTE: It is possible we exited the maze at the point that we entered
// (our solution should check for this possibility),
// but if our algorithm is correct, this will only happen if there
// was no other exit from the maze.
bool coordsAreEdge( const int & x, const int & y );
int main()
{
// /*
// Maze 1
char maze[ SIZE ][ SIZE ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
{'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
{'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };
int xStart = 2; // starting X and Y coordinates for maze
int yStart = 0;
Direction INITIAL_DIR = RIGHT;
// */
/*
// Maze 2
char maze[ SIZE ][ SIZE ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '.', '.'},
{'#', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'#', '.', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };
int xStart = 2; // starting X and Y coordinates for maze
int yStart = 11;
Direction INITIAL_DIR = LEFT;
*/
/*
// Maze 3
char maze[ SIZE ][ SIZE ] =
{ {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'#', '.', '#', '.', '#', '.', '.', '#', '#', '#', '.', '.'},
{'#', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
{'#', '.', '.', '.', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
{'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
{'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };
int xStart = 2; // starting X and Y coordinates for maze
int yStart = 11;
Direction INITIAL_DIR = LEFT;
*/
int x = xStart; // current X and Y coordinates
int y = yStart;
mazeTraversal( maze, xStart, yStart, x, y, INITIAL_DIR );
//printMaze( maze );
system("pause");
return 0;
} // end main
// This function prints the maze
void printMaze( const char maze[][ SIZE ] )
{
for ( int row = 0; row < SIZE; row++ )
{
for ( int col = 0; col < SIZE; col++ )
{
cout << maze[row][col] << ' ';
}
cout << '\n';
}
cout << "\nHit enter to see next move\n";
}
// This function is invoked recursively in the solution provided by the text.
void mazeTraversal( char maze[][ SIZE ], const int & xStart, const int & yStart,
const int & xCoord, const int & yCoord, const Direction & dir )
{
maze[xCoord][yCoord] = 'P';
printMaze( maze );
maze[xCoord][yCoord] = 'X';
static int count = 1;
int row = xCoord;
int col = yCoord;
Direction newDir = dir;
system("pause");
system("cls");
//switch
switch( dir )
{
case DOWN:
if ( validMove( maze, xCoord, yCoord - 1 ) )
{
if ( coordsAreEdge(xCoord, yCoord - 1 ) )
{
break;
}
mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
} else if ( validMove( maze, xCoord + 1, yCoord ) ){
mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, dir );
} else if ( validMove( maze, xCoord, yCoord + 1 ) ){
mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
} else {
mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
}
//break;
case RIGHT:
if ( validMove( maze, xCoord + 1, yCoord ) )
{
mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
} else if ( validMove( maze, xCoord, yCoord + 1 ) ){
if ( coordsAreEdge(xCoord, yCoord + 1 ) )
{
break;
}
mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, dir );
} else if ( validMove( maze, xCoord - 1, yCoord ) ){
mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
} else {
mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
}
//break;
case UP:
if ( validMove( maze, xCoord, yCoord + 1 ) )
{
if ( coordsAreEdge(xCoord, yCoord + 1 ) )
{
break;
}
mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
} else if ( validMove( maze, xCoord - 1, yCoord ) ){
mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, dir );
} else if ( validMove( maze, xCoord, yCoord - 1 ) ){
mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
} else {
mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
}
//break;
case LEFT:
if ( validMove( maze, xCoord - 1, yCoord ) )
{ mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
} else if ( validMove( maze, xCoord, yCoord - 1 ) ){
mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, dir );
} else if ( validMove( maze, xCoord + 1, yCoord ) ){
mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
} else {
mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
}
//break;
default:
cout << "Error: Direction must be 0, 1, 2, 3, or 4. dir = " << dir;
}
if ( (xCoord == xStart) && (yCoord + 1 == yStart) ){
maze[xCoord][yCoord + 1] = 'P';
maze[xCoord][yCoord] = 'X';
printMaze( maze );
cout << "\nArrived back at the starting location.\n";
} else {
maze[xCoord][yCoord + 1] = 'P';
maze[xCoord][yCoord] = 'X';
printMaze( maze );
cout << "\nMaze successfully exited!\n";
}
//switch( dir )
//{
// case DOWN:
// col--;
// if ( validMove( maze, row, col) )
// {
// if ( coordsAreEdge(row, col) )
// {
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (row == xStart) && (col == yStart) ){
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// cout << "Entering mazeTraversal: " << ++count << "\n";
// mazeTraversal( maze, xStart, yStart, row, col, LEFT );
// }
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, dir );
// }
// break;
// case RIGHT:
// row++; // Check pos below
// if ( validMove( maze, row, col) )
// {
// if ( coordsAreEdge(row, col) )
// {
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (row == xStart) && (col == yStart) ){
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// cout << "Entering mazeTraversal: " << ++count << "\n";
// mazeTraversal( maze, xStart, yStart, row, col, DOWN );
// }
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, dir );
// }
// break;
// case UP:
// col++;
// if ( validMove( maze, row, col) )
// {
// if ( coordsAreEdge(row, col) )
// {
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (row == xStart) && (col == yStart) ){
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// cout << "Entering mazeTraversal: " << ++count << "\n";
// mazeTraversal( maze, xStart, yStart, row, col, RIGHT );
// }
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, dir );
// }
// break;
// case LEFT:
// row--;
// if ( validMove( maze, row, col) )
// {
// if ( coordsAreEdge(row, col) )
// {
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (row == xStart) && (col == yStart) ){
// maze[row][col] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// cout << "Entering mazeTraversal: " << ++count << "\n";
// mazeTraversal( maze, xStart, yStart, row, col, UP );
// }
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, dir );
// }
// break;
// default:
// cout << "Default!!!\n";
//}
//switch( dir )
//{
// case DOWN:
// if ( validMove( maze, xCoord, yCoord - 1 ) )
// {
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
// } else if ( validMove( maze, xCoord + 1, yCoord ) ){
// mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, dir );
// } else if ( validMove( maze, xCoord, yCoord + 1 ) ){
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
// }
//
// //break;
//
// case RIGHT:
// if ( validMove( maze, xCoord + 1, yCoord ) )
// {
// if ( coordsAreEdge(xCoord + 1, yCoord ) )
// {
// maze[xCoord + 1][yCoord] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (xCoord + 1 == xStart) && (yCoord == yStart) ){
// maze[xCoord + 1][yCoord] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
// }
// } else if ( validMove( maze, xCoord, yCoord +1 ) ){
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, dir );
// } else if ( validMove( maze, xCoord - 1, yCoord ) ){
// mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
// }
//
// break;
//
// case UP:
// if ( validMove( maze, xCoord, yCoord + 1 ) )
// {
// if ( coordsAreEdge(xCoord, yCoord + 1) )
// {
// maze[xCoord][yCoord + 1] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nMaze successfully exited!\n";
// break;
// } else if ( (xCoord == xStart) && (yCoord + 1 == yStart) ){
// maze[xCoord][yCoord + 1] = 'P';
// maze[xCoord][yCoord] = 'X';
// printMaze( maze );
// cout << "\nArrived back at the starting location.\n";
// break;
// } else {
// //cout << "Entering mazeTRaveersal?!\n";
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
// }
//
// } else if ( validMove( maze, xCoord - 1, yCoord ) ){
// mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, dir );
// } else if ( validMove( maze, xCoord, yCoord - 1 ) ){
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, LEFT );
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
// }
// cout << "BREAK!\n";
// break;
//
// case LEFT:
// if ( validMove( maze, xCoord - 1, yCoord ) )
// { mazeTraversal( maze, xStart, yStart, xCoord - 1, yCoord, UP );
// } else if ( validMove( maze, xCoord, yCoord - 1 ) ){
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord - 1, dir );
// } else if ( validMove( maze, xCoord + 1, yCoord ) ){
// mazeTraversal( maze, xStart, yStart, xCoord + 1, yCoord, DOWN );
// } else {
// mazeTraversal( maze, xStart, yStart, xCoord, yCoord + 1, RIGHT );
// }
//
// //break;
//
// default:
// cout << "Error: Direction must be 0, 1, 2, 3, or 4. dir = " << dir;
//}
}
//This function returns 'true' if the move is valid
bool validMove( const char maze[][ SIZE ], const int & row, const int & col )
{
if ( maze[row][col] == '#' )
{
return false;
}
return true;
}
//This function returns 'true' if we have exited the maze.
//NOTE: It is possible we exited the maze at the point that we entered
// (our solution should check for this possibility),
// but if our algorithm is correct, this will only happen if there
// was no other exit from the maze.
bool coordsAreEdge( const int & x, const int & y )
{
if ( x == 0 || x == (SIZE-1) )
{
return true;
}
else if ( y == 0 || y == (SIZE-1) )
{
return true;
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment