Here is the question, homework is containing the stack library ( written by me ), inheritance, nested if, constructor, destructor. You can see the sample. I had 2 hours to finish and send , so it is not a perfect code. (Even i would have time, i don’t think i can write perfect code 
) Anyway, you can download cpp file from here, and here is stack file
Problem:
You are expected to find an escape route from a maze. The maze is inputted by user with 1’s and 0’s, where 1 represents a wall and 0 represents a road. Maze is a grid of cells, which can be considered as a 2-D array having cells. The start point for the maze is always at cell (1, 1) and exit from the maze will be always at cell (3, 3). (Consider a 5×5 matrix with walls in its outer boarders).
For finding the path, move from the starting cell and search for the neighbors of that cell by checking the cells in the directions North, East, South, and West. The search for the available neighbors will be in clockwise direction (so start checking North cell, then East cell,…)
Assume there is one possible route to exit.
Use class Cell to hold position and information for each cell in the maze grid as:
Classes:
class Cell
{ int row, column, direction;
bool visited;
int wallstatus; //could be 1 or 0
public:
//necessary members for the Cell
};
To play the game, create class Game:
class Game
{
//Matrix to hold the maze of cells
// Cell position of the goal
// Current Position on the Matrix
// Next Position of the Matrix
//Stack to hold the positions in the path
public:
//constructor to read the shape of the maze from user, and store it to the
matrix, and store the position of the goal. Then it will call the function to
traverse the maze
//function to perform the traversal
//function to calculate and return the next position using the table below
//function to set outer cells as wall.
//function to get all user input and generate the maze
//function to check whether you can move from current location or not
(direction<=3?)
//other necessary functions
};
Algorithm:
The maze traversal will be done using a stack. It will be used to store the cells for the route to the exit. The possible traversal algorithm will be as follows:
Start from (1,1) position, and set direction to 0
Push this cell to stack
While (stack is not empty && the goal is not found)
If you can’t move from current position and stack is not empty Pop () the stack
to go to the previous location
While (until all the directions are checked &&until the goal is not found)//there are available moves from current position
Find the nextrow and nextcolumn positions from the current direction
If (newrow and newcolumn is the goal)
Push the location and exit from loops
Else if (the new position is not a wall && it was not visited before)
{ Mark the new position as visited in the matrix
Check the next direction by updating it by 1
Push the new position with its row, column and direction to stack
Update current row& column with the new ones
Update direction as 0 to start searching for the available location
from north
}
Else
Check the next direction by updating the direction by 1
If (the goal is found)
While (stack not empty)
Pop the stack and output
Else
Maze does not have an exit
To calculate new row and column values to move in different directions, use the following table:
Direction
direction value
update for row
update for column
North
0
-1
0
East
1
0
1
South
2
1
0
West
3
0
-1
At the end of the game, the points for the escape route with their row and column values and the hop number required to escape will be displayed.
Sample Run: (For 5×5 mazes)
Enter the maze:
000
101
100
5 hops needed for escape
The cells to follow:
(1, 1)
(1, 2)
(2, 2)
(3, 2)
(3, 3)
The Maze Generated by User Input in the Sample Run:
<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
0
|
1
|
|
1
|
1
|
1
|
1
|
1
|
In the Sample run we say it’s a 5×5 matrix, but we get the input of a 3×3 matrix because the outside of the maze is always a wall which will not be inputted from the user. The Matrix above shows the final maze inputted by the user.
#include "oestack.h"
#include <iostream> // including library
using namespace std;
#include <string>
class cell
// class of cell
{
int row,column;
int visited;
int wallstatus;
public:
void addcell
(int a,
int b,
int c
) // which row, which column and also is it a wall, save this info.
{
row=a;
column=b;
wallstatus=c;
visited=
0;
}
void editvisit
() //for checking.
{
visited=
1;
}
int checkvisit
()
{
return visited;
}
int checkwall
()
{
return wallstatus;
}
int checkrow
()
{
return row;
}
int checkcolumn
()
{
return column;
}
};
class game:public cell
{
public:
stack<cell> stackcell; //created a stack type of cell
cell kop[5][5]; // created an array from cell object
game()
{
int l,z,i;
for(i=0; i<5; i++) // All cell is visited now, all of them is wall.
{
for(int k=0;k<5; k++)
{
kop[i][k].addcell(1,1,1);
}
}
cout<<"Enter maze from left to right:"<<endl<<"***"<<endl<<"***"<<endl<<"***"<<endl;
cout<<"Enter 1 for wall , 0 for gate, but like, 0 enter 1 enter 0 enter … (nine times)"<<endl; //You should write nine times,I didn’t use getch or smt like that so you have to write by one by
for(int j=1; j<4; j++) //Create 9 cell for maze , for each cell, write it is cell or wall. From left to right
{
for(l=1;l<4;l++)
{
cin>>z;
kop[j][l].addcell(l,j,z); //create
}
}
for(i=0; i<5; i++) // write our maze to the screen
{
for(int k=0;k<5; k++)
{
cout<<kop[i][k].checkwall();
}
cout<<endl;
}
}
void find_goal()
{
int i=1,k=1,found=0; // i and k is 1 because we start from cell (1,1)
cell start,back,yaz; // i need three object
stack<cell> terstenyaz(9); // to write from last
start = kop[i][k]; // start
kop[i][k].editvisit(); // you visited where you start.
stackcell.push(start); // put (1,1) (start place) to in your stack
while (found == 0) // found 0
{
if(kop[i][k].checkrow()==3 && kop[i][k].checkcolumn()==3) // if end of the maze
{
found =1; // find way to escape
}
else if(kop[i][k-1].checkwall() == 0 && kop[i][k-1].checkvisit() != 1) //check left , if not visited then go
{
k=k-1;
kop[i][k].editvisit();
stackcell.push(kop[i][k]);
}
else if(kop[i+1][k].checkwall() == 0 && kop[i+1][k].checkvisit() != 1) //check below , if not visited then go
{
i=i+1;
kop[i][k].editvisit();
stackcell.push(kop[i][k]);
}
else if(kop[i][k+1].checkwall() == 0 && kop[i][k+1].checkvisit() != 1) //check right , if not visited then go
{
k=k+1;
kop[i][k].editvisit();
stackcell.push(kop[i][k]);
}
else if (kop[i][k].checkrow() == 1 && kop[i][k].checkcolumn()== 1) // if you go back to start then there is no escape from maze
{
cout<<"No escape from there"<<endl;
found = 1;
}
else if(kop[i-1][k].checkwall() == 0 and kop[i-1][k].checkvisit() == 0) //check up , if not visited then go
{
i=i-1;
kop[i][k].editvisit();
stackcell.push(kop[i][k]);
}
else //if you can not go anywhere , go 1 cell back and check there is another way or not.
{
back = stackcell.pop();
i = back.checkrow();
k = back.checkcolumn();
}
}
if(found == 1) // escaped
{
while(stackcell.isEmpty() != 0) //to write from last to first, maybe recursive functions can be used,but i had no time to use it.
{
yaz = stackcell.pop();
terstenyaz.push(yaz);
}
while(terstenyaz.isEmpty() != 0) //write on screen
{
yaz=terstenyaz.pop();
cout<<"("<<yaz.checkcolumn()<<","<<yaz.checkrow()<<")"<<endl;
}
}
}
};
int main ()
{
game a; //call
a.find_goal();
getchar();
getchar();
}
Related posts
Recent Comments