solution for a maze*****important*****

[Ibrahim Ashraf]

/*This program should find a solution for a maze that is taken from an input file and take the entrance coordination and find the path to the exit.It doesn't want to work can someone help me.
That's an example for the input file.
Maze1
7,6
1,1,1,1,1,1
1,0,1,1,0,1
1,0,0,0,0,1
1,0,1,1,0,0
1,0,1,1,0,1
1,1,0,0,1,1
1,1,1,1,1,1
3 // number of entrances
1,2 // coordinate of an entrance relative to the origin: row, column
5,3
4,1
Maze2 // start of a new maze
3,10
1,1,1,1,1,1,0,1,1,1
1,0,0,1,1,0,0,1,1,1
1,1,1,1,1,1,1,1,1,1
2
1,1
1,5*/
#include<iostream>
#include<string>
#include<cstring>
#include<fstream>
using namespace std;

struct pos
{
int x;
int y;
};
struct stack
{
int index;
pos arr[500];
};
bool push( stack* Mystack ,pos position)
{ if (Mystack->index==500)
return false;
else
{
Mystack->arr[Mystack->index ]=position;
Mystack->index=Mystack->index+1;
return true;

}
}
bool stackIsEmpty(stack* Mystack)
{
if (Mystack->index == (-1))
{
return true;
}
else
{
return false;
}
}
void pop (stack *Mystack)
{ if (!(stackIsEmpty(Mystack)))
{
pos temp=Mystack->arr[Mystack->index];
Mystack->index=Mystack->index-1;


}

}
pos parent(stack* Mystack)
{
if (!Mystack->index==-1)
{
return Mystack->arr[Mystack->index-1];
}

}

bool**create_maze(int rows,int columns)
{
bool **a=new bool*[rows];
for (int row=0;row<rows;row++)
{
a[row]=new bool[columns];
}
return a;

}
void populate_maze(bool ** maze,ifstream& inputfile,int rows,int columns)
{
string line ;
int k,i,j;

for (i=0; i<rows; i++)
{ k=0;
inputfile>> line;
for( j=0; j<line.length(); j=j+2)
{
maze[i][k]=stoi(&line[j]);
k++;
}
}



}
pos exit_point(bool** matrix,int rows,int columns)
{

pos exit;

for (int j=0; j<columns;j++)
{
if (matrix[0][j]==0)
{
exit.x=0;
exit.y=j;
return exit;
}
if(matrix[rows-1][j]==0)
{
exit.x=rows-1;
exit.y=j;
return exit;
}
}
for (int i=0; i<rows;i++)
{

if (matrix[i][0]==0)
{
exit.x=i;
exit.y=0;
return exit;
}
if (matrix[i][columns-1]==0)
{
exit.x=0;
exit.y=columns-1;
return exit;
}

}
}
bool find_path(bool**maze, int x,int y, pos &position)
{
if (maze[x][y-1]==0)
{
position.x=x;
position.y=y-1;
return true;
}
if (maze[x][y+1]==0)
{
position.x=x;
position.y=y+1;
return true;
}
if (maze[x-1][y]==0)
{
position.x=x-1;
position.y=y;
return true;
}
if (maze[x+1][y]==0)
{
position.x=x+1;
position.y=y;
return true;
}

return false;
}

void main()
{
string trash , line ,dimensions;
ifstream inputmatrix;
inputmatrix.open("E:\\Ibrahim\\maze.txt");
ofstream outputmatrix;
outputmatrix.open("E:\\Ibrahim\\solution.txt");

while (!(inputmatrix.eof()))
{

getline(inputmatrix,trash);
inputmatrix>>line;
int commalocation =line.find(',');
string rows_str , cols_str;
rows_str=line.substr(0,commalocation);
cols_str=line.substr(commalocation+1);
cout<<rows_str<<" "<<cols_str;//checking t
int rows = stoi(rows_str);
int cols = stoi(cols_str);
bool** mymaze = create_maze(rows ,cols);
populate_maze(mymaze ,inputmatrix,rows,cols);
int maze=**mymaze;
inputmatrix>>line;
int no_entrances=stoi(line);
getline(inputmatrix,trash);
pos exit=exit_point(mymaze , rows , cols);
for(int i=0; i<no_entrances ;i++)
{
int x,y;
inputmatrix>>line;
int commalocation =line.find(',');
string rows_str , cols_str;
string entrance_x=line.substr(0,commalocation);
string entrance_y=line.substr(commalocation+1);
cout<<entrance_x<<" "<<entrance_y;//checking t
x=stoi(entrance_x),y=stoi(entrance_y);


//------start backtracking ---------------

pos Myposition,next_step;
Myposition.x=x;
Myposition.y=y;
stack visited;
push(&visited ,Myposition);
if( mymaze[x][y]==0)
{
while ( !( (Myposition.x== exit.x) &&(Myposition.y == exit.y) ) && !( stackIsEmpty(&visited) ) )
{
if (find_path(mymaze,Myposition.x,Myposition.y,next_step))
{
push(&visited , next_step);
mymaze[Myposition.x][Myposition.y]=1;
}

else
{
next_step=parent(&visited);
Myposition.x=next_step.x;
Myposition.y=next_step.y;

pop(&visited);
}

}
if(stackIsEmpty(&visited))
cout<<"entrance :"<<(i+1)<<":"<<x<<","<<y<<" trapped"<<endl;
if(!(stackIsEmpty(&visited)))
{
int u;
cout<<"entrance :"<<(i+1)<<":"<<x<<","<<y<<" ";
for (u=0;u>visited.index;u++)
{
// cout<<"("<<visited[1].x<<","<<visited[u].y<<")";

}
cout<<endl;
}
else
cout<<"entrance :"<<(i+1)<<":"<<x<<","<<y<<" invalid";
int mymaze=maze;

}


}


}
}