迷宫问题，以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对信任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
太久没好好动脑，搞这个搞到头晕晕，网上有不少，看得也是头晕晕，现在这个虽然还有些不足，没办法筛选最优路径，以后学多点知识后，再改进吧。
文件"mystack.h"
#include<iostream>
using namespace std;
class pos //迷宫中每个点的位置，所包含的数据
{
public:
int x;
int y;
int dir; //0:无效方向，1：上，2：右，3：下，4：左
};
class Node //结点类
{
public:
pos data;
Node *next;
friend class Stack;
};
class Stack
{
private:
Node *head;
public:
Stack()
{
head=NULL;
}
bool empty()
{
return (head==0);
}
void push(pos d)
{
Node *p=new Node;
p->data=d;
p->next=head;
head=p;
}
pos top()
{
if(empty())
{
cout<<"stack is empty."<<endl;
exit(0);
}
return head->data;
}
void pop()
{
Node *p=head;
head=head->next;
delete p;
}
};
文件"maze.h"
#include"mystack.h"
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定义当前位置移动的4个方向
//初始化迷宫
int **Getmaze(int &m,int &n)
{
int a,b;
int **maze;
int i=0,j=0;
cout<<"输入迷宫的长和宽：";
cin>>a>>b;
m=a;
n=b;
maze=new int *[m+2];
for(i=0;i<m+2;i++)
maze[i]=new int[n+2];
cout<<"请输入迷宫内容(0表示通，1表示不通)：";
//i,j都从1号位置开始，因为0号和m+1以及n+1要作为围墙
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>maze[i][j];
for(i=0;i<m+2;i++)
maze[i][0]=maze[i][n+1]=1;
for(i=0;i<n+2;i++)
maze[0][i]=maze[m+1][i]=1;
return maze;
}
//输出路线
void PrintPath(Stack p)//将p逆置回来，放在t里面
{
cout<<"迷宫路径为\n";
cout<<"括号内容分别表示（行，列，方向）\n";
Stack t;
int a,b;
pos data;
Node *temp;
temp=new Node();
temp->data=p.top();
p.pop();
t.push(temp->data);
delete temp;
while(!p.empty())
{
temp=new Node();
temp->data=p.top();
p.pop();
//获取方向dir
a=t.top().x-temp->data.x;
b=t.top().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.top();
t.pop();
cout<<'('<<data.x<<','<<data.y<<','; //输出行坐标，列坐标
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<<"end)\n";break;
}
}
}
//恢复原图
void Restore(int **maze,int m,int n)
{
int i,j;
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
if(maze[i][j]==-1)
maze[i][j]=0;
}
//寻找迷宫maze中从(0,0)到(m,n)的路径
bool Mazepath(int **maze,int m,int n)
{
Stack p,q;//p存储探索过程，q存储路径
pos t1,t2;
int x,y,loop;
t1.x=1;
t1.y=1;
q.push(t1);
p.push(t1);
maze[1][1]=-1;//用-1标志此点已到达
while(!q.empty())
{
t2=q.top();
if(!(p.top().x==t2.x&&p.top().y==t2.y))
p.push(t2);//如果有新位置入栈，则将其加入p
//探索当前的点的四个相邻位置
for(loop=0;loop<4;loop++)
{
x=t2.x+move[loop][0];
y=t2.y+move[loop][1];
if(maze[x][y]==0)//然后此点可通过
{
t1.x=x;
t1.y=y;
maze[x][y]=-1; //标志新位置已经到达
q.push(t1);
}
if((x==m)&&(y==n))//成功到达出口
{
t1.x=m;
t1.y=n;
t1.dir=0;
p.push(t1);
PrintPath(p);//输出路径
Restore(maze,m,n);//恢复原图
return 1;
}
}
//如果如果没有新路径入栈，则返回上一个位置
if( (p.top().x==q.top().x)&&(p.top().y==q.top().y) )
{
p.pop();
q.pop();
}
}
return 0;
}
测试代码"main.cpp"
#include"maze.h"
int main()
{
int m=0,n=0;
int **maze;
maze=Getmaze(m,n);
if(Mazepath(maze,m,n))
cout<<"迷宫路径搜索成功"<<endl;
else
cout<<"路径不存在"<<endl;
return 0;
}