struct offsets
{
Int a,b ;
};
Enum directions {N,NE,E,SE,S,SW,W,NW};
Offsets move[8] ;
While (stack is not empty)
{
(i,j,dir) = coordinates and direction deleted from top of stack;
While (there are more moves )
{
(g,h) = coordinates of next move;
if ((g == m)&&(h == p)) success;
if ((!maze [g][h]) // legal move
&& (!mark [g][h]) // have not been here before
{
Mark [g][h] = 1;
Dir = next direction to try;
Add (i,j,dir)to top of stack;
i=g; j=h; dir=north;
}
}
}
Cout <<"no path found "<<end1;
Void path(int m,int p)
// output a path(if any) in the maze ; maze [o][i] = maze [m+1][i] =
// maze [j][o] = maze [j][p+1] =1,0 ≤ i≤ p+1,0 ≤ j ≤ m+1.
{
// start at (1,1)
Mark [1][1] = 1;
Stack < items > stack ( m* p);
Items temp;
Temp.x = 1; temp.y =1; temp.dir = E;
Stack.Add(temp);
While (!stack.IsEmpty()) // stack not empty
{
Temp = *stack.delete(temp);//umstack
int i = temp.x; int j = temp.y;int d = temp.dir;
while(d<8)//move forward
{
int g = i + move [d] .a; int h = j +move [d] .b;
if ((g == m ) &&(h == p)) { // reached exit
// output path
cout << stack;
cout << i<<" "<< j<< end1; // last two squares on the path
cout << m<<" "<< p << end1;
return;
}
if ((!maze [g][h]) &&(!mark [g][h])){ // new position
mark [g][h] = 1;
temp.x = i; temp.y = j; temp.dir = d+1;
stack.Add(temp); // stack it
i = g; j = h; d = N; // move to ( g,h)
}
else d ++ ; // try next direction
}
}
Cout << " no path in maze " << end1;
Ostream & operator <<(ostream & os,stack < keyType>& s)
{
Os<<"top="<<s.top<<end1;
For(int i=o; i<=s.top; i++)
Os<<i<<":"<<s.stack[i]<< end1;
Return os;
}
Ostream& operator<<(ostream& os, items& item)
{
Return os<<item.x<<","<<item.y<<","<< item.dir;
}
نیاز فوری!
