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;

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

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

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

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

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