#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;

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

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

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

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

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