jindan.txt

经典的迷宫算法

#define OK 1
#define ERROR 0
#define NULL 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define INFEASIBLE -1
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREAMENT 10 //存储分配空间的分配增量
#define RANGE 100

#include<malloc.h>
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>


typedef int Status;
typedef struct {//定义坐标类型
int x; 
int y;
}PosType;

typedef struct {//定义栈的元素类型
int ord;//通道块在路径上的序号
PosType seat;//通道块在迷宫中的坐标位置
int di;//从此通道块走向下一通道块的方向
}SElemType;

typedef struct {//定义顺序存储的栈
SElemType * top;//栈顶指针
SElemType * base;
int stacksize;//当前已分配的存储空间
}SqStack;

typedef struct {//定义迷宫类型 
int m,n;
int maze[RANGE][RANGE]; //定义一个数组类型
}MazeType;

Status InitStack(SqStack &s)
{ //构造一个空栈 S

s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s.base) return (OVERFLOW);//存储分配失败
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;

}//InitStack

Status Push(SqStack &s,SElemType &e)
{//插入元素e为新的栈顶元素

SElemType * newbase;
if(s.top-s.base>=s.stacksize-1){//栈满，追加存储空间 
newbase=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!newbase) return(OVERFLOW);//存储分配失败
s.base=newbase;
s.top=s.base+s.stacksize-1;
s.stacksize+=STACKINCREAMENT;
}
*s.top++=e;
return OK;

}//Push

Status Pop(SqStack &s,SElemType &e)
{//若栈不空，则删除s的栈顶元素,成功返回TRUE，并返回其值为e,否则，返回ERROR

if(s.top==s.base) return ERROR;
e=*--s.top;
return OK;

}//Pop

Status StackEmpty(SqStack &s)
{//若栈为空，则返回OK,否则返回ERROR

if(s.base==s.top) 
return OK;
else 
return ERROR;

}//StackEmpty

Status Pass(MazeType &maze,PosType p)
{// 当坐标上的值为1时,可以通过,返回OK，否则返回ERROR
if(maze.maze[p.y][p.x]==1)
return OK;
else 
return ERROR;
}//Pass

void FootPrint(MazeType &maze,PosType &p)
{ //当位置可以通过时,把x赋值为2,留下痕迹

maze.maze[p.y][p.x]=2;

}//FootPrint

void MarkPrint(MazeType &maze,PosType &p)
{//当位置不可以通过时,把x赋值为3,留下痕迹

maze.maze[p.y][p.x]=3;

}//markPrint


void NextPos(PosType &e,int di)
{//寻找下一位置

switch (di){
case 1: e.x++;break;
case 2: e.y++;break;
case 3: e.x--;break;
case 4: e.y--;break;
}//switch

}//NextPos

Status MazePrint(MazeType maze)
{ //输出找路径后的迷宫图

cout<<"用图(1表示可以走过的位置,0表示不可通过的位置，)表示为:"<<endl;

for(int i=0;i<maze.m;i++){
for(int j=0;j<maze.n;j++)
cout<<maze.maze[i][j]<<' ';
cout<<endl;
}
return OK;

}//MazePrint

Status CreatMaze(MazeType &maze,PosType &start,PosType &end)
{
//当k等于1时，用户通过键盘输入 m,n创建m行,n列迷宫
//当k等于0时，调用一个已创建好的10行，10列的迷宫

int x; //建立创建迷宫还是调用已经建好的迷宫的标志位

cout<<"请选择是否自定义迷宫："<<endl;
cout<<"如果选择自定义创建m*n迷宫，请输入1；"<<endl<<"调用已经创建好的10*10迷宫,请输入0"<<endl;
cin>>x;
if(x==1) {
//对要求进行创建迷宫的人加以提示
cout<<"注意，在本程序中，用0表示迷宫的墙和障碍，用1表示可以通过的区域"<<endl;
cout<<"请输入迷宫的行数m:"<<endl;
cin>>maze.m;
cout<<"请输入迷宫的列数n:"<<endl;
cin>>maze.n;
int y=1; //建立数组行标志位
for(int i=0;i<maze.m;i++){ //录入迷宫图
printf("请输入第%d行的元素:",y);
cout<<endl;
for(int j=0;j<maze.n;j++)
cin>>maze.maze[i][j];
y++;
}
cout<<"请确认你输入的迷宫:"<<endl;
}
else if(x==0) { 
//创建默认的迷宫图
//建立中间转换数组变量
int a[10][10]={{0,0,0,0,0,0,0,0,0,0},{0,1,1,0,1,1,1,0,1,0},{0,1,1,0,1,1,1,0,1,0},
{0,1,1,1,1,0,0,1,1,0}, {0,1,0,0,0,1,1,1,1,0},{0,1,1,1,0,1,1,1,1,0},{0,1,0,1,1,1,0,1,1,0},
{0,1,0,0,0,1,0,0,1,0},{0,0,1,1,1,1,1,1,1,0},{0,0,0,0,0,0,0,0,0,0}};
maze.m=10; //行
maze.n=10; //列
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
maze.maze[i][j]=a[i][j];//建立默认迷宫地图
}
else {
cout<<"您输入了不合法的数值"<<endl;
return OK;
}

cout<<"您所默认或者所输入的迷宫图为下"<<endl; 
MazePrint(maze); //输出用户默认或者所输入的迷宫图

cout<<"注意坐标从<0,0>开始"<<endl;
cout<<"请输入入口坐标:"<<endl; //输入入口坐标
cin>>start.x; cin>>start.y;
cout<<"请输入出口坐标:"<<endl; 
cin>>end.x; cin>>end.y; //输入出口坐标
return OK;

}//CreatMaze

Status PosPrint(MazeType &maze,SqStack &s)
{ //用坐标输出走过的路经
cout<<"用坐标表示为:"<<endl;
int n=1; //建立路径步骤标志位
SElemType e;
SqStack s1;
InitStack(s1);
while(!StackEmpty(s)){//逆序------把栈s中的元素依次弹出,并依次压入栈s1中
Pop(s,e);
Push(s1,e);
}
while(!StackEmpty(s1)) {
//把栈s1中的元素依次弹出,并输出其每一步的坐标
Pop(s1,e);
printf("第%d步的坐标为:",n);
cout<<'('<<e.seat.x<<','<<e.seat.y<<')';
n++;
cout<<endl;
}
return OK;
}//PosPrint

Status MazePath(MazeType &maze, PosType start,PosType end,SqStack &s)
{ //寻找一条最近的迷宫图，并用栈s记录其路径 ，找到返回OK，否则，返回ERROR

PosType curpos;
int curstep=1;//探索第一步
SElemType e;

int k=0;
curpos.x=start.x;
curpos.y=start.y;
do
{
if (Pass(maze,curpos)){//当前位置可以通过，既是未曾走过的通道块
FootPrint(maze,curpos);//留下足迹
//把入口作为路径的第一步
e.di=1;
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
Push(s,e);//加入路径
if (curpos.x==end.x&&curpos.y==end.y) {
return OK;
k=1;
cout<<"在迷宫中,找到一条走过的路径:"<<endl;//到达端口
}
NextPos(curpos,1);//下一位置是当前位置的东邻
curstep++;//探索下一步
}//if
else{//当前位置不可能通过 
if(!StackEmpty(s)){
Pop (s,e);
while(e.di==4&&!StackEmpty(s)){
MarkPrint(maze,e.seat);//留下不能通过的标记，并退回一步
Pop(s,e);
}//while
if(e.di<=4){
e.di++;
Push(s,e);//换下一个方向探索
NextPos(e.seat,e.di);//设定当前位置随时该新方向上的相邻快
curpos.x=e.seat.x;
curpos.y=e.seat.y;

}//if
}//if
}//else
}while(!StackEmpty(s));
if(!k)cout<<"##############没有找到从入口到出口的路径##############"<<endl;
return FALSE;

}//MazePath


void main()
{//主函数

MazeType maze;
PosType end;
PosType start;
SqStack s;

InitStack(s); //初始化堆栈
CreatMaze(maze,start,end); //创建迷宫图并录入入点与出点
MazePath(maze,start,end,s); //寻找一条路径
PosPrint(maze,s); //打印出路径上的每一个点的坐标
cout<<"用图(2标记路径上的位置,3表示走过但是后面无法走过又返回的位置)表示为:"<<endl;
MazePrint(maze); //打印出走之后的迷宫图

}//main