#include<iostream.h>
#include<stdlib.h>
#include <stdio.h>
#include <time.h>
#include<conio.h>
#include"stack.h"
#include<conio.h>
#define R 32 //地图总行数
#define L 32 //地图总列数
#define r R-2 //可用的地图行数
#define l L-2 //可用的地图列数
typedef struct
{
int x;
int y;
}Node;//标示位置的节点类型
class RatInMase//老鼠和迷宫的主类
{
private:
stack<Node> *path; //定义一个栈存放Node节点
int seed;
int mase[R][L];
int stept;//查找的步数
public:
bool searchPath(int &i,int &j)
{
if(i==r&&j==l) return true;//找到并返回真
if(path->isFull()||path->isEmpty())//如果出现栈空或栈满的错误，将不能修复，只能退出
{
cout<<"系统发生不可修复的异常，请按任意键退出...";
getch();
exit(1);
}
else if(gotoEast(i,j))
{
Node thisnode,secondnode;
thisnode.x=i;
thisnode.y=j;
secondnode=path->getSecondNode();
if(secondnode.x==i&&secondnode.y==j)
{
mase[i][j-1]= 1; //?????????????????????????????????
path->pop();
}
else
path->push(thisnode);
searchPath(i,j);
}
else if(gotoSouth(i,j))//往南走
{
Node thisnode,secondnode;
thisnode.x=i;
thisnode.y=j;
secondnode=path->getSecondNode();
if(secondnode.x==i&&secondnode.y==j)
{
mase[i-1][j]=1;
path->pop();
}
else
path->push(thisnode);
searchPath(i,j);
}
else if(gotoWest(i,j))//往西走
{
Node thisnode,secondnode;
thisnode.x=i;
thisnode.y=j;
secondnode=path->getSecondNode();
if(secondnode.x==i&&secondnode.y==j)
{
mase[i][j+1]=1; //????????????????????????
path->pop();
}
else
path->push(thisnode);
searchPath(i,j);
}
else if(gotoNorth(i,j))//往北走
{
Node thisnode,secondnode;
thisnode.x=i;
thisnode.y=j;
secondnode=path->getSecondNode();
if(secondnode.x==i&&secondnode.y==j)
{
mase[i+1][j]=1;
path->pop();
}
else
path->push(thisnode);
searchPath(i,j);
}
else//如果没有出路了，而且返回了起点。说明没有出路了
return false;//返回假
}
void initMase() //每次执行时初始迷宫的所有设置
{
Node n;
n.x=1;
n.y=1;
seed=2;//初始化随机种子
stept=0;
path->clearStack();
path->push(n);
}
int getSteptCount()
{
return stept;
}
void print()
{Node n;
cout<<"老鼠找到的正确路线是："<<endl;
while(!path->isEmpty())
{ n=path->getTopNodeAndPop();
cout<<"("<<n.x <<","<<n.y<<"),";
}
}
int getStackDepth()
{
return path->getElementCount();
}
public :
RatInMase()
{
path=new stack<Node>(100 );//在试图动态分配栈的元素空间时失败！！！
if(path==NULL)
{
cout<<"内存分配失败！";
getch();
exit(1);
}
Node n;
n.x=1;
n.y=1;
seed=2;//初始化随机种子
stept=0;
path->push(n);
}
void setSeed(int &s)
{
seed=s;
}
createMap()
{
try{
for(int j=0;j<L;j++)
mase[0][j]=1;
for(j=0;j<L;j++)
mase[R-1][j]=1;
for(j=0;j<R;j++)
mase[j][0]=1;
for(j=0;j<R;j++)
mase[j][L-1]=1;//以上四个循环设立围墙
for(int i=1;i<=r;i++)
for(j=1;j<=l;j++)
{ srand(j*i*197%seed);//输入随机种子
mase[i][j]=rand()%2; //???????????????????????????
}
mase[1][1]=0;//设置入口
mase[r][l]=0;//设置出口
for(i=1;i<r;i++)
for(j=1;j<l;j++)
{if(i==j)
mase[i][j]=1; //????????????????????
if(i%3==0)
mase[i][j]=0;
}
for(j=1;j<r;j++)//为特定点设为开路
mase[j][1]=0;
for(j=3;j<l-2;j++)//为特定点设为开路
mase[5][j]=0;
for(j=3;j<l-2;j++)//为特定点设为开路
mase[j][2]=0;
mase[6][l/2]=1;
mase[4][8]=1;
mase[3][l]=1;
mase[r/2][l/2]=1;
mase[8][1]=1;
mase[r][l-1]=0;
mase[r-1][l]=0;
mase[r/3][l/4]=1;
mase[r-1][l-1]=0;//为特定点设为开路
cout<<"迷宫路线如下："<<endl;
for(i=0;i<R;i++)//输出迷宫地图
{
for(j=0;j<L;j++)
{
cout<<mase[j]<<" ";
}
cout<<endl;
}
}
catch(char)
{
cout<<"throw a exeception! "<<endl;
}
}
private:
bool gotoSouth(int& i,int& j )//向南走
{
if(mase[i+1][j]==0)
{
i=i+1;
cout<<"向南走..";//<<endl;
stept++;
return true;
}
else
return false;
}
bool gotoNorth(int& i,int& j)//向北走
{
if(mase[i-1][j]==0)
{
i=i-1;
cout<<"向北走..";//<<endl;
stept++;
return true;
}
else
return false;
}
bool gotoEast(int& i,int& j)//向东走
{
if(mase[j+1]==0)
{
j=j+1;
cout<<"向东走..";//<<endl;
stept++;
return true;
}
else
return false;
}
bool gotoWest(int& i,int &j)//向西走
{
if(mase[j-1]==0)
{
j=j-1;
cout<<"向西走..";//<<endl;
stept++;
return true;
}
else
return false;
}
};
void main()
{RatInMase rat;
int i=1,j=1,seed;
label://跳转标志
i=1;
j=1;
rat.initMase();//将老鼠走的步数初始为0
cout<<"请输入迷宫地图随机种子(必须是数字 嘿嘿...)：";
cin>>seed;
cout<<endl;
rat.setSeed(seed);
rat.createMap();
cout<<"正在查找请等待......."<<endl;
cout<<"老鼠的行踪如下："<<endl;
if(rat.searchPath(i,j))
{
cout<<endl<<" 哈哈 小KISS! 共用了"<<rat.getSteptCount()<<"步就找到出口找到路线了！"<<endl;
//cout<<"正确的路线的步数是："<<rat.getStackDepth()<<endl;
rat.print();
}
else
cout<<endl<<"靠！什么鬼地图啊！！全是死胡同。白费走了"<<rat.getSteptCount()<<"步都没有找到路线！重来一次吧！"<<endl;
cout<<endl<<"再来一次么？(y/n)";
char c;
cin>>c;
if(c=='y'||c=='Y') goto label;
else
{ getch();
exit(1);
}
}
评论0