On the bottom of this page I have a mostly written program that for some reason

Question

On the bottom of this page I have a mostly written program that for some reason compiles but freezes on run time (likely some logical error). Below are the general specifications for the program I need help on.

Generally the solution to the problem is something like this:
If row=10 & col= 10, then you have successfully escaped

Otherwise:
Try to escape via the South door
If not successful; Try to escape via the East door.
If not successful; Try to escape via the West door.
If not successful; Try to escape via the North door.
If you have successfully escaped from this position; then print out the current cell positions on your escape path list.

Watch out for cycles, which will cause end less loops because you repeatedly visit the same cell only to run around in a circle. You should visit each cell only once. Try to escape through all 4 doors; if not successful then this cell is a dead-end, the recursive call terminate for this cell.

When you've found an exit route, print the row/col coordinates of each cell on the route. The path you print will be in order, that is the first entry will be row=1, col=1 and the last entry will be row=10, col=10.

Don't worry about the 1s along the edges when the program runs: There are a safety wall of sorts and prevent false exits.

Read and Echo print the data file. (ratmaze.txt)

(File contents are as follows:)
0 1 1 1 0 1 0 0 1 1
0 0 0 0 0 0 1 1 1 1
0 1 1 1 1 0 1 0 1 1
0 0 0 0 1 0 0 0 1 1
1 1 1 0 1 1 1 0 0 1
1 1 1 0 1 0 0 1 1 1
1 1 0 0 1 1 1 0 0 1
0 0 0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 0 1 1
0 0 0 0 0 1 1 0 0 0
(You may need to make this into a text file of your own to see how the program runs.)

The program must use Recursion to find an exit path out of the maze.

The program must print out the escape route by row & col of cells used to exit.
Cells that are part of a dead end route, shouldn’t be included on the escape route. Change the value to something other than 0 or 1.

If there is no exit out of the maze, the program needs to print a message indicating as such.

Below is the code I have:
(further below is sample output of a successful run program with the given text file data.)


#include <iostream>
#include <cstring>
#include <fstream>
#include <iomanip>
using namespace std;

int maze[11][11];
void findExit(int row, int col, bool& success);
void initializeMaze (ifstream& inf);
void echoMaze();


int main()
{
string fname;
int row, col;
bool success = false;

cout << "Please enter maze data file name:" << endl; //prompts user to enter file name
cin >> fname; //accepts user input

ifstream inf;

inf.open(fname.c_str()); //opens user specified file

if(inf.fail()) //prints error message if user file failed to open
{
cout << "Input data file failed to open." << endl;
system("pause");
exit(1);
}
//Here file open OK

initializeMaze(inf);
findExit(row, col, success);

system("pause");
return 0;
}

void initializeMaze (ifstream& inf)
{
int row, col;
// fill whole maze with ones
for (row = 0; row < 12; row++)
for (col = 0; col < 12; col++)
maze [row][col] = 1;

cout << " Maze after all walls ";
echoMaze();

//now load maze with data
for (row = 1; row < 11; row++)
for (col = 1; col < 11; col++)
inf >> maze [row][col];

cout << " Maze after reading data we have ";
echoMaze();
}

//displays the current maze
void echoMaze()
{
int row, col;
//fill whole maze with ones
for (row = 0; row < 12; row++)
{
for (col = 0; col < 12; col++)
cout << maze [row][col] << " ";
cout << endl;
}
cout << endl;
}

void findExit(int row, int col, bool& success)
{
if (success)
{
cout << "Successful Exit!!" << endl;
cout << endl;
cout << "Escape path in order:" << endl;

if(( row == 10) && (col == 10))
{
cout << "Exit Route : " << " row = " << row << " col = " << col << endl;
success = true;
}


else if ((!success) && (maze[row][col + 1] == 0) )
{
cout << "=======>";
cout << "Exit Route : " << " row = " << row << " col = " << col << endl;
findExit(row, col + 1, success);

}

else if ((!success) && (maze[row + 1][col] == 0) )
{

cout << "=======>";
cout << "Exit Route : " << " row = " << row << " col = " << col << endl;
findExit(row + 1, col, success);

}

else if ((!success) && (maze[row - 1][col] == 0) )
{
cout << "=======>";
cout << "Exit Route : " << " row = " << row << " col = " << col << endl;
findExit(row - 1, col , success);
}

else ((!success) && (maze[row][col - 1] == 0) );
{
cout << "=======>";
cout << "Exit Route : " << " row = " << row << " col = " << col << endl;
findExit(row, col - 1, success);
}
}

else (!success);
{
cout << "There is no escape route from this maze." << endl;
}
}

The sample output for a successful program:

=======> Exit Route: row = 1 col = 1
=======> Exit Route: row = 2 col = 1
=======> Exit Route: row = 3 col = 1
=======> Exit Route: row = 4 col = 1
=======> Exit Route: row = 4 col = 2
=======> Exit Route: row = 4 col = 3
=======> Exit Route: row = 4 col = 4
=======> Exit Route: row = 5 col = 4
=======> Exit Route: row = 6 col = 4
=======> Exit Route: row = 7 col = 4
=======> Exit Route: row = 7 col = 3
=======> Exit Route: row = 8 col = 3
=======> Exit Route: row = 8 col = 2
=======> Exit Route: row = 8 col = 1
=======> Exit Route: row = 9 col = 1
=======> Exit Route: row = 10 col = 1
=======> Exit Route: row = 10 col = 2
=======> Exit Route: row = 10 col = 3
=======> Exit Route: row = 10 col = 4
=======> Exit Route: row = 8 col = 6
=======> Exit Route: row = 9 col = 5
=======> Exit Route: row = 8 col = 5
=======> Exit Route: row = 8 col = 6
=======> Exit Route: row = 8 col = 7
=======> Exit Route: row = 9 col = 7
=======> Exit Route: row = 9 col = 8
=======> Exit Route: row = 10 col = 8
=======> Exit Route: row = 10 col = 9
=======> Exit Route: row = 10 col = 10

Many thanks in advance for the help.

Explanation / Answer

Three things:
-The reason your program is crashing is because in main(), findExit(row, col, success);

should be findExit(1, 1, success); //only success has been initialized before, so you have to start of at grid position (1,1)

Also, I had to #include <cstdlib>

- Your order of movement is wrong. Remember, to move DOWN, you have to increment row, not col. So the sequence of your if statements (and corresponding findExit()s should be):

maze[row+1][col],

 maze[row][col+1],

 maze[row][col-1],

 maze[row-1][col],

corresponding to down, right, left and up.

 

-There is still the issue of re-visiting the cells, which you have not tackled as yet, that is, if compiled and run with your test maze, once it reaches cell (8,2), it sees that DOWN is blocked, and RIGHT is open, but it came from RIGHT, so there's an endless loop.

 

A temporary fix(that will only solve the current maze however) would be to add an extra parameter to the recursive function indicating the last direction. The function will then try to avoid the last path traveled and choose a new one instead. 

The if statements would then look like this:

else if ((!success) && (maze[row+1][col] == 0) && last!='u'){

cout << "=======>";cout << "Exit Route : " << " row = " << row << " col = " << col << endl;findExit(row+1, col, success,'d');

}

and the recursive call would have void findExit(int row, int col, bool& success, char last);

 

the extra char represents direction (u,d,l,r respectively)

The problem arises when one HAS TO BACKTRACK in order to get to the end of the maze. That's when this breaks down, but at least it's a starting point for you to improve your program.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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