计算机迷宫课题设计代码
- 格式：doc
- 大小：36.00 KB
- 文档页数：5
#include
using namespace std;
class T
{
public:
int x;
int y;
int dir;
};
class LinkNode
{
friend class Stack;
public:
T data;
LinkNode*next;
};
class Stack
{
private:
LinkNode*top;
public:
Stack();
-Stack();
void Push(T e);
T Pop();
T GetPop();
void Clear();
bool empty();
};
Stack::Stack()
{
top=NULL;
}
Stack::-Stack()
{
}
void Stack::Push(T e)
{
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=NULL;
}
bool Stack::empty()
{
if(top==NULL)return 1;
else return 0;
}
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool Mazepath(int**maze,int m,int n);
void PrintPath(Stack p);
void Restore(int**maze,int m,int n);
int**GetMaze(int &m,int &n);
int main()
{
int m=0,n=0;
int**maze;
maze=GetMaze(m,n);
if(Nazepath(maze,m,n))
cout<<"迷宫路径探索成功！/n";
else cout<<"迷宫路径不存在！/n";
return 0;
}
int**GetMaze(int &m,int &n)
{
int**maze;
int i=0,j=0;
cout<<"请输入迷宫的长和宽:"; int a,b;cin>>a>>b;
cout<<"请输入迷宫内容:/n";
m=a;
n=b;
maze=new int*[m+2];
for(i=0;i { maze[i]=new int*[n+2]; } for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>maze[i][j]; for(i=0;i maze[i][0]=maze[i][n+1]=1; for(i=0;i maze[0][i]=maze[m+1][i]=1; return maze; }; bool Mazepath(int**maze,int m,int n) { Stack q,p; 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() { Temp2=q.GetPop(); if(!p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) p.Push(Temp2); for(loop=0;loop<4;loop++) { x=Temp2.x+move[loop][0]; y=Temp2.y+move[loop][1]; 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; } void PrintPath(Stack p) { cout<<"迷宫的路径为/n"; cout<<"括号内的内容分别表示为（行坐标，列坐标，数字化方向，方向）/n"; Stack t; int a,b; T data; LinkNode*temp; temp=new LinkNode; temp->data=p.Pop(); t.Push(temp->data); delete temp; while(!p.empty()) { 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; else if(b==1)temp->data.dir=2; else if(a==-1)temp->data.dir=3; else if(b==-1)temp->data.dir=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 for(j=0;j { if(maze[i][j]==-1) maze[i][j]=0; } }
