#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdlib>
#include<windows.h>
#define Yes 1
#define NO 0
#define Mazesize 9
#define TRUE 1
using namespace std;
char maze[Mazesize][Mazesize]
{
{'1','1','1','1','1','1','1','1','1'},
{'1','0','1','0','0','0','1','1','1'},
{'1','0','1','1','1','0','1','0','1'},
{'1','0','1','0','0','0','1','0','1'},
{'1','0','1','0','0','1','1','0','1'},
{'1','0','0','0','0','0','0','0','1'},
{'1','0','1','0','1','1','1','1','1'},
{'1','0','1','0','0','0','0','0','1'},
{'1','1','1','1','1','1','1','1','1'}
};
class Position//坐标
{
public:
int x;
int y;
};
class Stackelem:public Position//路径元素 ........包含所有迷宫处理
{
public:
int order; //顺序
int direction;
Position Pos;
Stackelem()//初始化函数
{
direction = 0;
}
int NextDir()//转换方向
{
direction++;
if(direction == 5) return 0;
return direction;
}
void MarkPos(int Judge)//标记所过路径
{
switch(Judge)
{
case Yes: maze[Pos.x][Pos.y] = '.';break;
case NO: maze[Pos.x][Pos.y] = '#';break;
default: cout<<"错误...";break;
}
}
void NextPos()//移动位置
{
Stackelem nextpos;
switch(direction)
{
case 0: break;
case 1: Pos.x++; break;
case 2: Pos.y--; break;
case 3: Pos.x--; break;
case 4: Pos.y++; break;
default:cout<<"大大的错误"<<endl;
}
}
bool canPass()//判断是否通过
{
if(maze[Pos.x][Pos.y] == '0') return true;
else return false;
}
};
class Stack:public Stackelem//包含所有栈处理
{
public:
int top;
Stackelem *base;
int Stacksize;
Stack()//构造函数
{
Stacksize = Mazesize * Mazesize;
base = new Stackelem[Stacksize];
if(!base)
{
cout<<"内存分配失败"<<endl;
exit(OVERFLOW);
}
else
cout<<"初始化成功"<<endl;
top = 0;
}
int Pop_Stack();//弹出栈顶
int Push_Stack(Stackelem e);//推入栈顶
bool Empty_Stack(); //判断栈是否为空
Stackelem gettop()
{
return base[top-1];
}
void Visit_Stack()
{
system("cls");
int t = 0;
cout<<endl;
cout<<"("<<base[t].Pos.x<<", "<<base[t].Pos.y<<")";
for(t=1;t<top;t++)
cout<<" -> ("<<base[t].Pos.x<<", "<<base[t].Pos.y<<")";
cout<<endl;
}
};
int Stack::Pop_Stack()//弹出栈顶元素
{
if(top == 0)
{
cout<<"栈空..."<<endl;
return ERROR;
}
top--;
return 0;
}
int Stack::Push_Stack(Stackelem e)//把元素推入栈顶
{
if(top<Stacksize)
{
base[top] = e;
top++;
return TRUE;
}else
{
cout<<"栈满..."<<endl;
}
}
bool Stack::Empty_Stack()//判断栈是否为空
{
if(top == 0) return true;
else return false;
}
void Printmaze()//打印迷宫
{
cout<<"迷宫......"<<endl;
for(int i=0;i<Mazesize;i++)
{
for(int j=0;j<Mazesize;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
}
void Find_Path()//寻路函数
{
int num = 1;
Stack s;
Stackelem e, nexe, start, end;
start.Pos.x = start.Pos.y = 0;
end.Pos.x = end.Pos.y = 0;
while(maze[start.Pos.x][start.Pos.y]!='0'||maze[end.Pos.x][end.Pos.y]!='0')
{
cout<<"请输入初始位置";
cin>>start.Pos.x>>start.Pos.y;
cout<<"请输入结束位置";
cin>>end.Pos.x>>end.Pos.y;
}
Sleep(1000); //暂停1秒钟
system("cls"); //清屏
e = start;
while(e.Pos.x!=end.Pos.x||e.Pos.y!=end.Pos.y)
{
if(e.canPass()&&num==1)
{
s.Push_Stack(e);
e.MarkPos(Yes);
}
else
{
if(!s.Empty_Stack())
{
s.Pop_Stack();
e = s.gettop();
}
else
{
cout<<"错误..."<<endl;
exit (0);
}
}
e.direction = 0;
do
{
nexe = e;
nexe.NextPos();
}while(!nexe.canPass()&&e.NextDir()!=0);
if(nexe.canPass())
{
e.direction--;
e = nexe;
num = 1;
cout<<"win...";
}
else
{
e.MarkPos(NO);
num = 0;
cout<<"OMG...";
}
Sleep(1000); //暂停1秒钟
system("cls"); //清屏
Printmaze();
}
s.Push_Stack(end);
end.MarkPos(Yes);
Sleep(1000); //暂停1秒钟
system("cls"); //清屏
Printmaze();
cout<<endl<<"任意键继续....."<<endl;
char c;
cin>>c;
s.Visit_Stack();
}
int main()
{
Printmaze();
Find_Path();
Printmaze();
return 0;
}
数据结构实验代码迷宫.rar
需积分: 5 132 浏览量
2024-05-01
20:32:35
上传
评论 1
收藏 355KB RAR 举报
温柔-的-女汉子
- 粉丝: 1027
- 资源: 4013