It is a 12X12 character array containing \'0\' (at places you can go) or \'1\' a

ID: 3684315 • Letter: I

Question

It is a 12X12 character array containing '0' (at places you can go) or '1' at places where you can't. You may assume that there is exactly one entrance and at least 1 exit to the maze (You Can give maximum 3 exits and minimum 1 exit). Create a Maze by random with 0's and 1's and give it exactly one entrance and at-least one exit (maximum: 3), the entry and exit points should be generated by random as well. As you can see, the generated maze has no possible exit. You have to programmatically determine this by traversing it. And you have to recreate the maze as many times as it takes to generate a solvable maze. This Program should have three possible outputs, Case 1: Maze exited successfully upon traversal. Case 2: Arrived back at the starting entry location upon traversal. Case 3: Generated maze has no possible exit. Use Recursion concept to solve the Maze. Create an enumerated data type Direction for all possible directions enemy Direction { DOWN, RIGHT, UP, LEFT} Refer HW 4 for random number/char generation. Create functions for Maze Generation, Maze Traversal, Printing Maze, Valid Move Check and Edge Check. In a 2D array, Traversal can be done like this. Current Position: (x, y) Down: (x+1, y) Right: (x, y + 1) Up: (x-1, y) Left: (x, y - 1]

Explanation / Answer

/** C++ Mase Runner **/
// 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.

#include <iostream>
#include <cstdlib>
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 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 ] =
{ {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
{'1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1'},
{'1', '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '1'},
{'1', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0'},
{'1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
{'1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'},
{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'} };

int xStart = 2; // starting X and Y coordinates for maze
int yStart = 0;
Direction INITIAL_DIR = RIGHT;

// */

// Maze 2
char maze[ SIZE ][ SIZE ] =
{ {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
{'1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '0'},
{'1', '1', '1', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'1', '0', '0', '0', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
{'1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0'},
{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'} };

int xStart = 2; // starting X and Y coordinates for maze
int yStart = 11;
Direction INITIAL_DIR = LEFT;

// Maze 3
char maze[ SIZE ][ SIZE ] =
{ {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
{'1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '0'},
{'1', '1', '1', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'1', '0', '0', '0', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '1', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
{'1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'},
{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'} };

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

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 << ' ';
   }
} // end of printMaze function

// 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 )
{
   //static int count = 1;
   int row = xCoord;
   int col = yCoord;
   Direction newDir = dir;

   switch( dir )
   {
       case DOWN:
           if ( validMove( maze, xCoord, yCoord - 1 ) )
           {
               col--;
               newDir = LEFT;
               break;

           } else if ( validMove( maze, xCoord + 1, yCoord ) ){
               row++;
               break;

           } else if ( validMove( maze, xCoord, yCoord + 1 ) ){
               col++;
               newDir = RIGHT;
               break;

           } else {
               row--;
               newDir = UP;
               break;
           }

       case RIGHT:
           if ( validMove( maze, xCoord + 1, yCoord ) ){
               row++;
               newDir = DOWN;
               break;

           } else if ( validMove( maze, xCoord, yCoord + 1 ) ){
               col++;
               break;

           } else if ( validMove( maze, xCoord - 1, yCoord ) ){
               row--;
               newDir = UP;
               break;

           } else {
               col--;
               newDir = LEFT;
               break;
           }

       case UP:
           if ( validMove( maze, xCoord, yCoord + 1 ) ){
               col++;
               newDir = RIGHT;
               break;

           } else if ( validMove( maze, xCoord - 1, yCoord ) ){
               row--;
               break;

           } else if ( validMove( maze, xCoord, yCoord - 1 ) ){
               col--;
               newDir = LEFT;
               break;

           } else {
               row++;
               newDir = DOWN;
               break;
           }

       case LEFT:
           if ( validMove( maze, xCoord - 1, yCoord ) ){
               row--;
               newDir = UP;
               break;

           } else if ( validMove( maze, xCoord, yCoord - 1 ) ){
               col--;
               break;

           } else if ( validMove( maze, xCoord + 1, yCoord ) ){
               row++;
               newDir = DOWN;
               break;

           } else {
               col++;
               newDir = RIGHT;
               break;
           }

       default:
           cout << "Error: Direction must be 0, 1, 2, or 3. dir = " << dir;
           break;
   }

   if ( coordsAreEdge( row, col ) )
   {
       if ( (row == xStart) && (col == yStart) ){
           maze[row][col] = 'P';
           maze[xCoord][yCoord] = 'X';
           printMaze( maze );
           cout << " Arrived back at the starting location. ";
       } else {

           maze[row][col] = 'P';
           maze[xCoord][yCoord] = 'X';
           printMaze( maze );
           cout << " Maze successfully exited! ";
       }
   } else {
       maze[xCoord][yCoord] = 'P';
       printMaze( maze );
       maze[xCoord][yCoord] = 'X';
       cout << " Hit enter to see next move ";
       system("pause");
       //system("cls");
       mazeTraversal( maze, xStart, yStart, row, col, newDir );
   }

} // End of mazeTraversal function

//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] == '1' )
   {
       return false;
   }

return true;
} // end of validMove function

//This function returns 'true' if we have exited 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;
} // end of coordAreEdge function

Navigate

It is Thanksgiving and the king decides to let out a few prisoners. He sends out

It is a C language programme for morse code. Just need the function and main cod

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

It is a 12X12 character array containing \'0\' (at places you can go) or \'1\' a

Question

Explanation / Answer

Related Questions

Navigate