Question

An excellent example of a program that can be greatly simplified by the use of recursion is the Chapter 4 case study, escaping a maze. As already explained, in each maze cell the mouse stores on the maze stack up to four cells neighboring the cell in which it is currently located. The cells put on the stack are the ones that should be investigated after reaching a dead end. It does the same for each visited cell. Write a program that uses recursion to solve the maze problem. Use the following pseudocode:

exitCell(currentCell)

if currentCell is the exit

  success;

  else exitCell(the passage above currentCell);

  exitCell(the passage below currentCell);

exitCell(the passage left to currentCell);

  exitCell(the passage right to currentCell);

Here is the code from the Chapter 4 Case Study:

#include <iostream>

#include <string>

#include <stack>

using namespace std;

template<class T>

class Stack : public stack<T> {

public:

T pop() {

T tmp = top();

stack<T>::pop();

return tmp;

}

};

class Cell {

public:

Cell(int i = 0, int j = 0) {

x = i; y = j;

}

bool operator== (const Cell& c) const {

return x == c.x && y == c.y;

}

private:

int x, y;

friend class Maze;

};

class Maze {

public:

Maze();

void exitMaze();

private:

Cell currentCell, exitCell, entryCell;

const char exitMarker, entryMarker, visited, passage, wall;

Stack<Cell> mazeStack;

char **store; // array of strings;

void pushUnvisited(int,int);

int rows, cols;

friend ostream& operator<< (ostream& out, const Maze& maze) {

for (int row = 0; row <= maze.rows+1; row++)

out << maze.store[row] << endl;

out << endl;

return out;

}

};

Maze::Maze() : exitMarker('e'), entryMarker('m'), visited('.'),

passage('0'), wall('1') {

Stack<char*> mazeRows;

char str[80], *s;

int col, row = 0;

cout << "Enter a rectangular maze using the following "

<< "characters:\nm - entry\ne - exit\n1 - wall\n0 - passage\n"

<< "Enter one line at at time; end with Ctrl-z:\n";

while (cin >> str) {

row++;

cols = strlen(str);

s = new char[cols+3]; // two more cells for borderline columns;

mazeRows.push(s);

strcpy(s+1,str);

s[0] = s[cols+1] = wall; // fill the borderline cells with 1s;

s[cols+2] = '\0';

if (strchr(s,exitMarker) != 0) {

exitCell.x = row;

exitCell.y = strchr(s,exitMarker) - s;

}

if (strchr(s,entryMarker) != 0) {

entryCell.x = row;

entryCell.y = strchr(s,entryMarker) - s;

}

}

rows = row;

store = new char*[rows+2]; // create a 1D array of pointers;

store[0] = new char[cols+3]; // a borderline row;

for ( ; !mazeRows.empty(); row--) {

store[row] = mazeRows.pop();

}

store[rows+1] = new char[cols+3]; // another borderline row;

store[0][cols+2] = store[rows+1][cols+2] = '\0';

for (col = 0; col <= cols+1; col++) {

store[0][col] = wall; // fill the borderline rows with 1s;

store[rows+1][col] = wall;

}

}

void Maze::pushUnvisited(int row, int col) {

if (store[row][col] == passage || store[row][col] == exitMarker) {

mazeStack.push(Cell(row,col));

}

}

void Maze::exitMaze() {

int row, col;

currentCell = entryCell;

while (!(currentCell == exitCell)) {

row = currentCell.x;

col = currentCell.y;

cout << *this; // print a snapshot;

if (!(currentCell == entryCell))

store[row][col] = visited;

pushUnvisited(row-1,col);

pushUnvisited(row+1,col);

pushUnvisited(row,col-1);

pushUnvisited(row,col+1);

if (mazeStack.empty()) {

cout << *this;

cout << "Failure\n";

return;

}

else currentCell = mazeStack.pop();

}

cout << *this;

cout << "Success\n";

}

int main() {

Maze().exitMaze();

return 0;

｝

Answer 1

The answer of the above problem is given below :

#include <iostream>
#include <string.h>
#include <stack>

using namespace std;
template<class T>
class Stack : public stack<T>
{
public:
T pop()
{
T tmp = stack<T>::top();
stack<T>::pop();
return tmp;
}
};

class Cell
{
public:
/*Constructor function for Cell */
Cell(int i = 0, int j = 0)
{
x = i;
y = j;
}
/*Operator overloading for "==" */
bool operator == (const Cell& c) const
{
return x == c.x && y == c.y;
}

private:
int x, y;
/*A friend class can access private and protected
members of other class in which it is declared as friend.*/
friend class Maze;
};

class Maze
{
public:
Maze();
void exitMaze();
private:
Cell currentCell, exitCell, entryCell;
const char exitMarker, entryMarker, visited, passage, wall;
Stack<Cell> mazeStack;
char **store;
void pushUnvisited(int,int);
int rows, cols;

/*Operator overloading for "<<" to support stream insertion of Maze object */
friend ostream& operator << (ostream& out, const Maze& maze)
{
for (int row = 0; row <= maze.rows+1; row++)
out << maze.store[row] << endl;
out << endl;
return out;
}
};

Maze::Maze() : exitMarker('E'), entryMarker('M'), visited('.'),
passage('0'), wall('1')
{
Stack<char*> mazeRows;
char str[80], *s;
int col, row = 0;
cout << "Enter a Rectangular Maze Using the following "
<< "Characters:\nM - Entry\nE - Exit\n1 - Wall\n0 - Passage\n"
<< "Enter one line at at time; end with Ctrl-z:\n";

/*Insert the Maze pattern */
while (cin >> str)
{
row++;
cols = strlen(str);

/*two more cells for borderline columns;*/
s = new char[cols+3];
mazeRows.push(s);
strcpy(s+1,str);

/* fill the borderline cells with 1s;*/
s[0] = s[cols+1] = wall;
s[cols+2] = '\0';

if (strchr(s,exitMarker) != 0)
{
exitCell.x = row;
exitCell.y = strchr(s,exitMarker) - s;
}
if (strchr(s,entryMarker) != 0)
{
entryCell.x = row;
entryCell.y = strchr(s,entryMarker) - s;
}
}
rows = row;
store = new char*[rows+2]; /* create a 1D array of pointers; */
store[0] = new char[cols+3]; /*a borderline row; */
for ( ; !mazeRows.empty(); row--)
{
store[row] = mazeRows.pop();
}
store[rows+1] = new char[cols+3]; /*another borderline row; */
store[0][cols+2] = store[rows+1][cols+2] = '\0';

for (col = 0; col <= cols+1; col++)
{
store[0][col] = wall; /* fill the top borderline row with 1s;*/
store[rows+1][col] = wall; /* fill the bottom borderline row with 1s;*/
}
}

void Maze::pushUnvisited(int row, int col)
{
/*If Current cell is either passage Cell or exit Cell
then push it to the Stack */
if (store[row][col] == passage || store[row][col] == exitMarker)
{
mazeStack.push(Cell(row,col));
}
}

void Maze::exitMaze()
{
int row, col;
currentCell = entryCell;

/*Actual iteration to solve the Maze problem */
while (!(currentCell == exitCell))
{
row = currentCell.x;
col = currentCell.y;

/* cout << *this; */

if (!(currentCell == entryCell))
store[row][col] = visited;

/*Visit neighboring Cell for Solution */
pushUnvisited(row-1,col);
pushUnvisited(row+1,col);
pushUnvisited(row,col-1);
pushUnvisited(row,col+1);

/*If Stack is Empty means all the connected passage
from Entry cell has been Visited */
if (mazeStack.empty())
{
cout << *this;
cout << "Failure\n";
return;
}
else
currentCell = mazeStack.pop();
}
cout << *this;
cout << "Success\n";
}
/*Driver Function */
int main()
{
Maze().exitMaze();
return 0;
}
The screenshots of the code are as below :

Output Screen of the code is :

Thanks for liking the post.

For any query related to the post , Please comment !!!