In this program, I am trying to print a solution for the maze with '*' indicating a wall, ' ' indicating a corridor, and '#' indicating a solution path. I am using a recursive backtracking algorithm in this program. For instance, here is a small (8-by-12) maze:
8 12
**********
* * *
* ****** *
***** *
* ******
*** *** *
* ** *
**********
Here is the same maze printed showing the solution:
##**********
*#*########*
*###******#*
*****######*
* ###******
***#***####*
* #####**#*
**********##
Here is my code:
#include<iostream>
#include<fstream>
using namespace std;
#define MAXROW 24
#define MAXCOL 81
char a[MAXROW][MAXCOL];
int rows, columns;
void readMaze(ifstream &in)
{
in >> rows >> columns;
cout << rows << " " << columns << endl;
in.getline(a[0],sizeof a[0]);
for(int i = 0; i < rows; i++)
{
in.getline(a[i], sizeof a[i]);
}
}
void printMaze()
{
for(int i = 0; i < rows; i++)
{
cout << a[i] << endl;
}
}
bool solveMaze(int rows, int columns)
{
if(rows < 0 || rows > MAXCOL-1 || columns < 0 || columns > MAXROW-1)
{
return false;
}
if(a[columns][rows] == '*')
{
return false;
}
a[columns][rows] = '#';
if(solveMaze(rows, columns-1))
{
return true;
}
if(solveMaze(rows+1, columns))
{
return true;
}
if(solveMaze(rows, columns+1))
{
return true;
}
if(solveMaze(rows-1, columns))
{
return true;
}
a[columns][rows] = 'x';
return false;
}
int main()
{
char inFile[20] = "maze.txt";
ifstream in;
int rows = 0, columns = 0;
cout << "Enter file name: ";
cin >> inFile;
if(!inFile)
{
cout << "Error" << endl;
return 1;
}
in.open(inFile);
cout << "Maze before solve: " << endl;
readMaze(in);
printMaze();
cout << "Maze after: " << endl;
solveMaze(rows,columns);
printMaze();
in.close();
return 0;
}
The only thing I am having trouble with is printing the solution path. I don't know what I am doing wrong in this program. There could be something wrong in the solveMaze() function. What do I need to change in this program in order to print the solution path?