include
using namespace std;class t/定义描述迷宫中当前位置的结构类型
{
public:
int x;x代表当前位置的行坐标
int y;y代表当前位置的列坐标
int dir;0:无效,1:东,2:南,3:西,4:北
};class linknode/链表结点
{
friend class stack;public:
t data;linknode*next;};class stack
{
private:
linknode*top;指向第一个结点的栈顶指针
public:
stack();构造函数，置空栈
stack()/析构函数
{}
void push(t e);元素data入栈中
t pop();栈顶元素出栈
t getpop();取出栈顶元素
void clear();把栈清空
bool empty();判断栈是否为空，如果为空则返回1，否则返回0
};stack:stack()/构造函数，置空栈
{
top=**;}
void stack:push(t e)/元素x入栈中
{
linknode*p;p=new linknode;p->data=e;p->next=top;top=p;}
t stack:pop()/栈顶元素出栈
{
t temp;linknode*p;p=top;top=top->next;temp=p->data;delete p;return temp;}
t stack:getpop()/取出栈顶元素
{
return top->data;}
void stack:clear()/把栈清空
{
top=**;}
bool stack:empty()/判断栈是否为空，如果为空则返回1，否则返回0
{
if(top=**)return 1;else return 0;}
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};定义当前位置移动的4个方向
void printpath(stack p)/输出路径
{
cout迷宫的路径为\n;cout括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n;stack t;定义一个栈，按从入口到出口存取路径
int a,b;t data;linknode*temp;temp=new linknode;获取空间
temp->data=p.pop();取栈p的顶点元素，即第一个位置
t.push(temp->data);第一个位置入栈t
delete temp;释放空间
while!p.empty())/如果栈p非空，则反复转移
{
temp=new linknode;temp->data=p.pop();获取下一个位置
得到行走方向
a=t.getpop().x-temp->data.x;行坐标方向
b=t.getpop().y-temp->data.y;列坐标方向
if(a=1)temp->data.dir=1;方向向下，用1表示
else if(b=1)temp->data.dir=2;方向向右，用2表示
else if(a=-1)temp->data.dir=3;方向向上，用3表示
else if(b=-1)temp->data.dir=4;方向向左，用4表示
t.push(temp->data);把新位置入栈
delete temp;}/输出路径，包括行坐标，列坐标，下一个位置方向
while!t.empty())/栈非空，继续输出
{
data=t.pop();cout(',',',;输出行坐标，列坐标
switch(data.dir)/输出相应的方向
{
case 1:cout↓)\n;break;case 2:cout→)\n;break;case 3:cout↑)\n;break;case 4:cout←)\n;break;case 0:cout)\n;break;}
}
}
void restore(int*maze,int m,int n)/恢复迷宫
{
int i,j;for(i=0;i;i+)/遍历指针
for(j=0;j;j+)
{
if(maze[i][j]=-1)/恢复探索过位置，即把-1恢复为0
maze[i][j]=0;}
}
int*getmaze(int&m,int&n)/返回存取迷宫的二维指针
{
int*maze;定义二维指针存取迷宫
int i=0,j=0;cout请输入迷宫的长和宽:;int a,b;cin>>a>>b;输入迷宫的长和宽
cout请输入迷宫内容:(0为通路，1为墙)\n;m=a;n=b;m,n分别代表迷宫的行数和列数
maze=new int*[m+2];获取长度等于行数加2的二级指针
for(i=0;i;i+)/每个二维指针的空间
{
maze[i]=new int[n+2];}
for(i=1;i;i+)/输入迷宫的内容，0代表可通，1代表不通
for(j=1;j;j+)
cin>>maze[i][j];for(i=0;i;i+)
maze[i][0]=maze[i][n+1]=1;for(i=0;i;i+)
maze[0][i]=maze[m+1][i]=1;return maze;返回存贮迷宫的二维指针maze
};bool mazepath(int*maze,int m,int n)/寻找迷宫maze中从（0，0）到（m,n）的路径
{
stack q,p;定义栈p、q,分别存探索迷宫的过程和存储路径
t temp1,temp2;int x,y,loop;temp1.x=1;temp1.y=1;q.push(temp1);将入口位置入栈
p.push(temp1);maze[1][1]=-1;标志入口位置已到达过
while!q.empty())/栈q非空，则反复探索
{
temp2=q.getpop();获取栈顶元素
if!(((p.getpop().x)=(q.getpop().x))&((p.getpop().y)=(q.getpop().y))))
p.push(temp2);如果有新位置入栈，则把上一个探索的位置存入栈p
for(loop=0;loop;loop+)/探索当前位置的4个相邻位置
{
x=temp2.x+move[loop][0];计算出新位置x位置值
y=temp2.y+move[loop][1];计算出新位置y位置值
if(maze[x][y]=0)/判断新位置是否可达
{
temp1.x=x;temp1.y=y;maze[x][y]=-1;标志新位置已到达过
q.push(temp1);新位置入栈
}
if((x=(m))&(y=(n)))/成功到达出口
{
temp1.x=m;temp1.y=n;temp1.dir=0;p.push(temp1);把最后一个位置入栈
printpath(p);输出路径
restore(maze,m,n);恢复路径
return 1;表示成功找到路径
}
}
if(p.getpop().x=q.getpop().x&p.getpop().y=q.getpop().y)/如果没有新位置入栈，则返回到上一个位置
{
p.pop();q.pop();}
}
return 0;表示查找失败，即迷宫无路经
}
int main()
{
int m=0,n=0;定义迷宫的长和宽
int*maze;定义二维指针存取迷宫
maze=getmaze(m,n);调用getmaze(int&m,int&n)函数，得到迷宫
if(mazepath(maze,m,n))/调用mazepath(int*maze,int m,int n)函数获取路径
cout迷宫路径探索成功!\n;else cout路径不存在!\n;return 0;}
输入数据：
搜索的路径为：