-
backtracking!!
HELLO EVERYONE, I have an assignment question in which i have to find all the poosible solution to solve a maze.I need to build the algorithm through recursion.I have done it for single path but now i have to find all the possible paths.For this,i guess,i have to open all the "visited" cells again so that in backtracking,function again goes through another path.
My question is that where should i "open" all the "visited cells again so that while backtracking,function receives it as "unvisited".I am pasting my code here.
Code:
#include <iostream>
#include <fstream>
using namespace std;
/* ============================= */
/* ===== Global Variables ===== */
/* ============================= */
enum gameStatus {pending, success, impossible};
/* =============================== */
/* ===== Function Prototypes ===== */
/* =============================== */
void ReadMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese);
void DrawMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese);
void EscapeMaze(char Maze[10][10], int cpx, int cpy, const int spx, const int spy, const int epx, const int epy,
const int hbx, const int hby, gameStatus& status,int& nosol,int row,int col,int cheese,int mouse);
/* ========================= */
/* ===== Main Function ===== */
/* ========================= */
int main()
{
system("cls");
// Defining maze array and positioning variables
int row,col,mouse,cheese;
char Maze[10][10];
ReadMaze(Maze,row,col,mouse,cheese);
cout<<row<<col<<mouse<<cheese<<endl;
for (int i=0;i<row;i++)
{
for (int j=0;j<col;j++)
{
cout<<Maze[row][col]<<endl;
}
}
int spx = mouse;
int spy = col-1;
int epy = 0;
int epx = 0;
int hbx = 0;
int hby = 0;
int cpx = spx;
int cpy = spy;
int nosol = 0;
// Defining status variable and setting its initial value
gameStatus status;
status = pending;
EscapeMaze(Maze, cpx, cpy, spx, spy, epx, epy, hbx, by,status,nosol,row,col,cheese,mouse);
cout<<"solutions:"<<nosol<<endl;
if (status == impossible)
cout << "No path exists" << endl;
else
DrawMaze(Maze,row,col,mouse,cheese);
system("pause");
return 0;
} /* end main */
/* ================================ */
/* ===== Function Definitions ===== */
/* ================================ */
void ReadMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese)
{
int m = -1,n = 0;
ifstream ifile;
ifile.open("input.txt");
ifile>>row;
ifile>>col;
ifile>>mouse;
ifile>>cheese;
while(!ifile.eof())
{
m++;
for (int n = 0; n < col ; n++)
{
ifile >> Maze[m][n];
} /* end for */
} /* end while */
ifile.close();
// cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
} /* end ReadMaze */
void DrawMaze(char Maze[10][10],int& row,int& col,int& mouse,int& cheese)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cout << Maze[i][j] << " ";
} /* end for */
cout << endl;
} /* end for */
} /* end DrawMaze */
void EscapeMaze(char Maze[10][10], int cpx, int cpy, const int spx, const int spy, const int epx, const int epy,
const int hbx, const int hby, gameStatus& status,int& nosol,int row,int col,int cheese,int mouse)
{
DrawMaze(Maze,row,col,mouse,cheese);
cout<<endl;
// system("pause");
if (cpx <= row && cpy <= col && cpx >= hbx && cpy >= hby)
{
if (cpx == cheese && cpy == cheese)
{
Maze[cheese][cheese] = '*';
status = success;
nosol++;
} /* end if */
else
{
Maze[cpy][cpx] = '*';
// Check positions for all directions
if ((Maze[cpy][cpx+1] == '0') || (Maze[cpy][cpx+1] == 'X'))
EscapeMaze(Maze, cpx+1, cpy, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // right
if ((Maze[cpy][cpx+2] == '0') || (Maze[cpy][cpx+2] == 'X'))
EscapeMaze(Maze, cpx+2, cpy, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // right
if ((Maze[cpy][cpx-1] == '0') || (Maze[cpy][cpx-1] == 'X'))
EscapeMaze(Maze, cpx-1, cpy, spx, spy, epx, epy, hbx, hby, status, nosol,row, col, cheese,mouse); // left
if ((Maze[cpy][cpx-2] == '0') || (Maze[cpy][cpx-2] == 'X'))
EscapeMaze(Maze, cpx-2, cpy, spx, spy, epx, epy, hbx, hby, status, nosol,row, col, cheese,mouse); // left
if ((Maze[cpy-1][cpx] == '0') || (Maze[cpy-1][cpx] == 'X'))
EscapeMaze(Maze, cpx, cpy-1, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // up
if ((Maze[cpy-2][cpx] == '0') || (Maze[cpy-2][cpx] == 'X'))
EscapeMaze(Maze, cpx, cpy-2, spx, spy, epx, epy, hbx, hby, status, nosol, row, col, cheese,mouse); // up
Maze[cpy][cpx] = '0'; //I think here it should "open" again..
if (status != success)
{
if (cpx == spx && cpy == spy)
status = impossible;
Maze[cpy][cpx] = '1';
} /* end if */
} /* end else */
} /* end if */
} /* end EscapeMaze */
The main problem is in Escape maze function.Can anyone tell me that where should i "open" the cells again?
-
I'm not sure how you are representing the maze data. But you need to be keeping track of the steps you have taken as you traverse the maze. You could have an array, and each time you take a step, add to the array, indicating which direction you just went. At the beginning of the recursive function, add the step you are taking, and at the end of the function, remove it. When you find a successful path, just use the data in the array, and print it out.
-
personally, I think its easier than you are making it. You solve it recursively by basically saying
the shortest path from the current cell to the exit is the shortest path among the neighboring cells that haven't already been checked, unless one of those cells is the exit, in which case that is the shortest path.
-
Here is what my maze look like
X 0 C
0 0 C
C 0 M
I have to start from "M" and should reach to "X".But my code runs only for single path.
-
Code:
fun( )
here = used
if here is exit
win
if unused north
fun( north )
if unused east
fun( east )
if unused south
fun( south )
if unused west
fun( west )
dead end, return
That's pretty much all you need.
Quzah.
-
