You are on page 1of 6

#include<iostream> #include<fstream> #include <string> using namespace std; ifstream rff("maze.

txt");//rff:ReadFromFile ofstream ptf("mazesolution.txt");//ptf:Print To File struct point { int row; int col; }; struct node { point data; node*next; }; struct stack { node*top; int count; }; bool isEmpty(stack*&s) { if (s->count==0) return true; else return false; } bool isFull(stack*&s) { node*temp = new node; if (temp==0) return true; else return false; } bool push(stack*&s,point p) { if (isFull(s)==false) { node*temp= new node; temp->data.row= p.row; temp->data.col= p.col; temp->next=s->top; s->top=temp; s->count ++; return true; } else return false; } bool pop(stack*&s,point&p) { if (isEmpty(s)==false) { p.row=s->top->data.row; p.col=s->top->data.col; s->count --; node*temp=s->top; s->top=s->top->next;

j=0.i<row. } else if(i==r-1&&j !=c-1)// in the last row but not the last colu . } bool createStack(stack*&s) { s=new stack. s->count=0. point p.j<col*2-1. return true. for(int i=0. return true.point&p) { if (isEmpty(s)==false) { p. } else return false. p. for (int i=0.i++) maze[i]= new int[col].int col) { maze = new int*[row]. } void createArray(int** &maze.int col) { char ch.delete temp. } else return false.int row.int row.row. for(int j=0.j++) { if(j%2==0) { rff>>M[i][counter].col. } else rff>>ch.int r.i++) { int counter=0.col=s->top->data. } } } point findExit(int**M. while (M[i][j] !=0) { if ( j==0&&i!=r-1)//in the first column and not reaching the las t row { i++. } bool top(stack*&s.row=s->top->data.i<row. return true. s->top=NULL. counter++.int c) { int i=0. } void enterMatrix (int **&M.

} bool isInvalid(int **A.point pos ) { int count=0.point size) { if( (pos.point pos. if (M[pos.row=i. for (int i=0.row][pos.col||pos. else if(i==1) pos.row<0||pos. else if(i==2) pos.col--. else if(i==2) . } else if(j==c-1&& i!=0)//in the last column but not the first row { i--. if(i==0) pos.row>=size.col--.row--. } bool isContinue(int**M.col>=size.i<4. } else if (i==0 && j!=0)//in the first row still searching for the exit j--. } return (count==1). else return false. return p. point c=pos.int &control ) { int count=0.mn { j++.col]==1) return true.row++.col]==0) count++. if(i==0) pos.row||pos.row][pos. else pos. for (int i=0. p.i++) { pos=c.i++) { pos=c.point pos.col++. } bool isIntersection(int **&M.col++. else if(i==1) pos. if( i==0 && j==0)// no exit at all break. else if(A[pos.i<4. } p.col=j.col<0))//outsi de the matrix return true. point c=pos.

mouse. else if(i==1) pos. decision.point mouse. for (int j=1. if (i==0) pos. } int control. point c_p.decision).row][pos.col !=pos.//any visited spot will be equal 2 so as no t to be passed more than once top(visited. return.row++.i++) { pos=c_p.row++. } control=count. if (Maze[pos . else pos.col) { if (isContinue(Maze.point size) { if (isInvalid(Maze.pos). point pos. stack *visited.row=-1. if (M[pos.i<4. . Maze[pos.pos. point decision.mouse).col]=2.row || dest.//Saves last visited position. else pos. break.pos)) { top(visited. for (int i=0. push(visited. while (dest.c_p).col]==0) { push(visited.row][pos.row][mouse.*alt. createStack(alt). Maze[mouse.row!=pos. decision . } void path(int **Maze.point dest.col=-1.pos.pos).col++. return (count>1). createStack(visited).col]=2.row--.row][pos.col]==0) count++.j++) { push(visited.//Control number of decisions.size))//checking whether the mouse is in a wron g place or not { ptf<<"Invalid".control)) { top(visited.c_p).col--. } } } else if(isIntersection(Maze.j<control. else if (i==2) pos.row--.

} else { if(isEmpty(alt)) { ptf<<"Trapped".row && pos.col) { pop(visited. createStack(path).col]= 4. else if(i==1) pos. .col)//removing decision tokens { push(path. Maze[pos. if (pos.i++) { pos=c_p. push(visited.pos). if(pos. if (i==0) pos.pos).pos). } while(pos. Maze[pos.col) { Maze[pos.pos).col]=3. } } while (!isEmpty(path)) { pop(path.row++.row][pos.row--. return.row][pos.row][pos.col--.i<4. else pos.row][pos.col !=decision.pos).row != decision.col++. while (!isEmpty(visited)) { pop(visited.col ! =decision.col]==0) { push(alt.row ||pos. push(visited.row!=decision.col]=2.pos). } }//Reaching exit stack *path.} for (int i=0. Maze[pos.//so as not to take any alternative twice in the same stack } } pop(alt.pos). else if (i==2) pos. if (Maze[pos .col]=2.col !=decisio n.row][pos.pos).row ||pos .pos).row!=decision. } } pop(alt.

rff>>size. for(int i=1.row<<".size. ptf<<endl. ptf<<endl.i<=n. int n.size.int row) { for (int i=0. enterMatrix(M.col<<" ". ptf<<mazename. } } } .row. char ch.size). rff>>n. if (!isEmpty(path)) { ptf<<"-"<<" ". } } } void deleteMat(int **M.row<<ch<<mouse. point dest=findExit(M.ptf<<"("<<pos.size.row.col).i++) { point mouse.dest. } int main() { while(!rff.col).col<<")"<<" ". string mazename.mouse.row.i++) { delete M[i]. rff>>ch. rff>>mazename.col."<<pos.size.size.eof()) { int **M=NULL. rff>>mouse.row. path(M. rff>>mouse. point size.row. createArray(M.size. ptf<<endl<<endl. rff>>ch.i<row. } delete M.col. ptf<<"Entrance:"<<" "<<mouse.col). rff>>size.