抖腿表情包:谁能用非递归算法解决老鼠走迷宫问题?我要源程序.!!!

#include<iostream>
#include<string>
#include<ctime>
#include<cstring>
using namespace std;

struct coordinate
{
int x,y;
int dir;
};

class stack
{
public:
coordinate *c;
int MaxSize;
int top;
stack(int);
void Push(const coordinate&);
coordinate Pop();
bool empty();
void Output();
};

stack::stack(int ms)
{
if(ms<=0){cerr<<"invalid ms"<<endl;exit(1);}
MaxSize=ms;
c=new coordinate[MaxSize];
if(!c)
{
cerr<<"memory allocation failure"<<endl;
exit(1);
}
top=-1;
}

void stack::Push(const coordinate& coor)
{
if(top==MaxSize)
{
cerr<<"stackoverflow"<<endl;
exit(1);
}
top++;
c[top]=coor;
}

coordinate stack::Pop()
{
if(top==-1)
{
cerr<<"stack is empty"<<endl;
exit(1);
}
top--;
return c[top+1];
}



bool stack::empty()
{
return top==-1;
}

void stack::Output()
{
while(!empty())
{
cout<<c[top].x<<' '<<c[top].y<<endl;
top--;
}
}

int main()
{
clock_t t1,t2,t3;
t1=clock();
int i,j,m,n,M,N,k,f;
cin>>M>>N>>i>>j>>m>>n;
stack S(M*N),R(M*N);
bool Mazepath(char**,int**,int,int,int,int,int,int,stack,stack);
int mazePath(char**,int**,int,int,int,int,int,int,stack);
cin.ignore();
int **mark=new int*[M+1];
char **maze=new char*[M+1];
for(k=0;k<M;k++) 
{
maze[k]=new char[N+1];
mark[k]=new int[N+1];
}
for(k=0;k<M;k++) cin.getline(maze[k],N+1,'\n');
for(k=0;k<M;k++)
for(f=0;f<N;f++) mark[k][f]=0;
t3=clock();
Mazepath(maze,mark,M,N,i,j,m,n,R,S);
//mazePath(maze,mark,M,N,i,j,m,n,S);
t2=clock();
cerr<<(double)(t3-t1)/CLK_TCK<<endl;
cerr<<(double)(t2-t3)/CLK_TCK;
for(k=0;k<M;k++) delete[]maze[k];
delete[]maze;
for(k=0;k<M;k++) delete[]mark[k];
delete[]mark;
delete[]S.c;
}

int mazePath(char** maze,int** mark,int M,int N,int i,int j,int m,int n,stack S)
{
coordinate coor={i,j,0};
int g,h;
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
while((!S.empty())||(coor.dir!=3))
{
g=coor.x+move[coor.dir][0];
h=coor.y+move[coor.dir][1];
if((g==m)&&(h==n)&&(maze[g][h]=='0'))
{
S.Push(coor);
coor.x=m;coor.y=n;coor.dir=0;
S.Push(coor);
while(!S.empty()) S.Output();
return 1;
}
else if((mark[g][h]==0)&&(maze[g][h]=='0'))
{
mark[g][h]=1;
S.Push(coor);
coor.x=g;coor.y=h;coor.dir=0;
}
else
{
if(coor.dir<3) coor.dir++;
else 
{
while((coor.dir==3)&&(!S.empty())) coor=S.Pop();
}
}
}
cerr<<"no path"<<endl;
return 0;
}

用栈嘛