您所在位置：主题：迷宫求解！！！
无怨无悔39
[专家分：0] 发布于 2010-12-20 19:22:00
#include<iostream.h>
#include<string.h>
#define STACK_INIT_SIZE 20 //储存空间初始分配量
#define M 10
#define N 10
typedef enum{
RIGHT,RIGHTDOWN,DOWN,LEFTDOWN,LEFT,LEFTUP,UP,RIGHTUP
}Direction;
typedef enum{
YES,NO
}MarkTag;
typedef struct position //迷宫中位置的坐标
{
int x;
int y;
}Position;
typedef struct SElemType
{
int order; //当前位置在路径中的序号
Position seat; //当前位置在迷宫中的坐标
Direction di; //从当前位置走到下一位置的方向
}SElemType; //栈元素的类型
typedef struct Stack
{
SElemType *base,*top;
int stacksize;
}Stack;
int InitStack(Stack &S) //初始化栈的函数
{//构造一个空栈
S.base=(SElemType *)new int(STACK_INIT_SIZE); //为S.base分配空间大小为20*2字节空间
if(!S.base) return true; //如果S.base 为空推出。
S.top=S.base; //不为空时则S.top=S.base. S.stacksize就赋值为20
S.stacksize=STACK_INIT_SIZE;
return true; //返回1
}
int Push(Stack &S,SElemType e) //元素e入栈
{
if(S.top-S.base>=S.stacksize)
return false;
*S.top++ =e; //S为对象，其属性top为指针先算 *S.top=e; 再 S.top++
return true;
}
int Pop(Stack &S,SElemType &e) //栈顶元素出栈，由e带回栈顶元素
{
if(S.top==S.base)
return false;
e=*--S.top; //S为对象，其属性top为指针先算 *S.top=e; 再 S.top++
return true;
}
int Empty(Stack S) //判断栈是否为空
{
if(S.top==0)
return true;
else
return false;
}
int CreateMaze(Position startpos,Position endpos)
{
Position start,end;
cout<<"请输入迷宫入口的位置：";
cin>>start.x>>start.y;
cout<<"请输入迷宫出口的位置：";
cin>>end.x>>end.y;
startpos=start; endpos=end;
return true;
} //createMaze
char maze[M+2][N+2]={
{'1','1','1','1','1','1','1','1','1','1','1'},
{'1','0','1','0','0','1','1','1','0','0','1'},
{'1','0','0','0','0','0','1','0','0','1','1'},
{'1','0','1','1','1','0','0','0','1','1','1'},
{'1','0','0','0','1','0','1','1','0','1','1'},
{'1','1','0','0','1','0','1','1','0','0','1'},
{'1','1','1','0','0','0','0','0','0','0','1'},
{'1','1','1','1','1','1','1','1','1','1','1'}
}; //用二维字符数组表示迷宫
int Pass(Position curpos)
{
if(maze[curpos.x][curpos.y]=='0')
return true;
else
return false;
}
void MarkPos(Position curpos,MarkTag tag) //为已经探索过的位置加标记
{
if(tag=YES)
maze[curpos.x][curpos.y]='.';//可以通过的路径标记
else
maze[curpos.x][curpos.y]='#'; //不可以通过的路径标记
}
//根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
Position NextPos(Position curpos,Direction di)
{ Position nextpos;
switch(di)
{
case RIGHT:nextpos.x=curpos.x;nextpos.y =curpos.y+1; break;
case RIGHTDOWN:nextpos.x=curpos.x+1;nextpos.y=curpos.y+1; break;
case DOWN :nextpos.x=curpos.x+1;nextpos.y =curpos.y; break;
case LEFTDOWN:nextpos.x=curpos.x+1;nextpos.y=curpos.y-1; break;
case LEFT :nextpos.x=curpos.x;nextpos.y =curpos.y-1; break;
case LEFTUP:nextpos.x=curpos.x-1;nextpos.y=curpos.y-1; break;
case UP :nextpos.x=curpos.x-1;nextpos.y =curpos.y; break;
case RIGHTUP:nextpos.x=curpos.x-1;nextpos.y=curpos.y+1; break;
}
return nextpos;
}
Direction NextDir(Direction di)
{ switch(di)
{
case RIGHT: return RIGHTDOWN;
case RIGHTDOWN : return DOWN;
case DOWN: return LEFTDOWN;
case LEFTDOWN: return LEFT;
case LEFT: return LEFTUP;
case LEFTUP:return UP;
case UP: return RIGHTUP;
}
return di;
}
int MazePath(Stack S,Position start,Position end)
{//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中（从栈底到栈顶），并返回true；若迷宫中不存在从入口start到出口end的通道，则返回false
Position curpos;
SElemType e;
int curstep=1; //探索第一步
if(InitStack(S)==false)
return false;
curpos=start; //设定“当前位置”为“入口位置”
do{
if(Pass(curpos)){ //当前位置可以通过
MarkPos(curpos,YES); //留下足迹
e.order=curstep,e.seat=curpos,e.di=RIGHT;
Push(S,e); //当前位置加入到路径，入栈
if(curpos.x==end.x&&curpos.y==end.y) //当前位置是出口
return true;
curpos=NextPos(curpos,RIGHT); //下一位置是当前位置的东邻，即右边
curstep++; //探索下一步
}
else{ //当前位置不能通过
if(!Empty(S)){
Pop(S,e);
while(!Empty(S)){
//八个方向都试探过，没有找到通路，只能回朔
curpos=e.seat;
MarkPos(curpos,NO);
}//while
if(e.di==RIGHTUP){//八个方向还没有探索完成
e.di=NextDir(e.di);
Push(S,e); //换下一个方向探索
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
}while(!Empty(S));
return false;
}
void main()
{
Position startpos,endpos;
Stack path;
int i,j;
SElemType e;
if(CreateMaze(startpos,endpos)==false)
return ;
MazePath(path,startpos,endpos);
while(!Empty(path)){ //输出出口到入口的路径
Pop(path,e);
cout<<e.seat.x<<e.seat.y;
}
//输出迷宫的图形
cout<<endl;
for(i=0;i<=12;i++)
{
for(j=0;j<=12;j++)
cout<<maze[i][j]<<endl;
}
}
编译之后提示有三个警告，但是多编译几次的话，就会没有错误和警告。然而执行的时候，就会遇到错误弹出窗口！不晓得哪里有问题了！求哪位高手帮个忙，或者我加你QQ，我还有很多不懂的地方想请教！谢谢...
#include<string.h>
#define STACK_INIT_SIZE 20 //储存空间初始分配量
#define M 10
#define N 10
typedef enum{
RIGHT,RIGHTDOWN,DOWN,LEFTDOWN,LEFT,LEFTUP,UP,RIGHTUP
}Direction;
typedef enum{
YES,NO
}MarkTag;
typedef struct position //迷宫中位置的坐标
{
int x;
int y;
}Position;
typedef struct SElemType
{
int order; //当前位置在路径中的序号
Position seat; //当前位置在迷宫中的坐标
Direction di; //从当前位置走到下一位置的方向
}SElemType; //栈元素的类型
typedef struct Stack
{
SElemType *base,*top;
int stacksize;
}Stack;
int InitStack(Stack &S) //初始化栈的函数
{//构造一个空栈
S.base=(SElemType *)new int(STACK_INIT_SIZE); //为S.base分配空间大小为20*2字节空间
if(!S.base) return true; //如果S.base 为空推出。
S.top=S.base; //不为空时则S.top=S.base. S.stacksize就赋值为20
S.stacksize=STACK_INIT_SIZE;
return true; //返回1
}
int Push(Stack &S,SElemType e) //元素e入栈
{
if(S.top-S.base>=S.stacksize)
return false;
*S.top++ =e; //S为对象，其属性top为指针先算 *S.top=e; 再 S.top++
return true;
}
int Pop(Stack &S,SElemType &e) //栈顶元素出栈，由e带回栈顶元素
{
if(S.top==S.base)
return false;
e=*--S.top; //S为对象，其属性top为指针先算 *S.top=e; 再 S.top++
return true;
}
int Empty(Stack S) //判断栈是否为空
{
if(S.top==0)
return true;
else
return false;
}
int CreateMaze(Position startpos,Position endpos)
{
Position start,end;
cout<<"请输入迷宫入口的位置：";
cin>>start.x>>start.y;
cout<<"请输入迷宫出口的位置：";
cin>>end.x>>end.y;
startpos=start; endpos=end;
return true;
} //createMaze
char maze[M+2][N+2]={
{'1','1','1','1','1','1','1','1','1','1','1'},
{'1','0','1','0','0','1','1','1','0','0','1'},
{'1','0','0','0','0','0','1','0','0','1','1'},
{'1','0','1','1','1','0','0','0','1','1','1'},
{'1','0','0','0','1','0','1','1','0','1','1'},
{'1','1','0','0','1','0','1','1','0','0','1'},
{'1','1','1','0','0','0','0','0','0','0','1'},
{'1','1','1','1','1','1','1','1','1','1','1'}
}; //用二维字符数组表示迷宫
int Pass(Position curpos)
{
if(maze[curpos.x][curpos.y]=='0')
return true;
else
return false;
}
void MarkPos(Position curpos,MarkTag tag) //为已经探索过的位置加标记
{
if(tag=YES)
maze[curpos.x][curpos.y]='.';//可以通过的路径标记
else
maze[curpos.x][curpos.y]='#'; //不可以通过的路径标记
}
//根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
Position NextPos(Position curpos,Direction di)
{ Position nextpos;
switch(di)
{
case RIGHT:nextpos.x=curpos.x;nextpos.y =curpos.y+1; break;
case RIGHTDOWN:nextpos.x=curpos.x+1;nextpos.y=curpos.y+1; break;
case DOWN :nextpos.x=curpos.x+1;nextpos.y =curpos.y; break;
case LEFTDOWN:nextpos.x=curpos.x+1;nextpos.y=curpos.y-1; break;
case LEFT :nextpos.x=curpos.x;nextpos.y =curpos.y-1; break;
case LEFTUP:nextpos.x=curpos.x-1;nextpos.y=curpos.y-1; break;
case UP :nextpos.x=curpos.x-1;nextpos.y =curpos.y; break;
case RIGHTUP:nextpos.x=curpos.x-1;nextpos.y=curpos.y+1; break;
}
return nextpos;
}
Direction NextDir(Direction di)
{ switch(di)
{
case RIGHT: return RIGHTDOWN;
case RIGHTDOWN : return DOWN;
case DOWN: return LEFTDOWN;
case LEFTDOWN: return LEFT;
case LEFT: return LEFTUP;
case LEFTUP:return UP;
case UP: return RIGHTUP;
}
return di;
}
int MazePath(Stack S,Position start,Position end)
{//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中（从栈底到栈顶），并返回true；若迷宫中不存在从入口start到出口end的通道，则返回false
Position curpos;
SElemType e;
int curstep=1; //探索第一步
if(InitStack(S)==false)
return false;
curpos=start; //设定“当前位置”为“入口位置”
do{
if(Pass(curpos)){ //当前位置可以通过
MarkPos(curpos,YES); //留下足迹
e.order=curstep,e.seat=curpos,e.di=RIGHT;
Push(S,e); //当前位置加入到路径，入栈
if(curpos.x==end.x&&curpos.y==end.y) //当前位置是出口
return true;
curpos=NextPos(curpos,RIGHT); //下一位置是当前位置的东邻，即右边
curstep++; //探索下一步
}
else{ //当前位置不能通过
if(!Empty(S)){
Pop(S,e);
while(!Empty(S)){
//八个方向都试探过，没有找到通路，只能回朔
curpos=e.seat;
MarkPos(curpos,NO);
}//while
if(e.di==RIGHTUP){//八个方向还没有探索完成
e.di=NextDir(e.di);
Push(S,e); //换下一个方向探索
curpos=NextPos(e.seat,e.di);
}//if
}//if
}//else
}while(!Empty(S));
return false;
}
void main()
{
Position startpos,endpos;
Stack path;
int i,j;
SElemType e;
if(CreateMaze(startpos,endpos)==false)
return ;
MazePath(path,startpos,endpos);
while(!Empty(path)){ //输出出口到入口的路径
Pop(path,e);
cout<<e.seat.x<<e.seat.y;
}
//输出迷宫的图形
cout<<endl;
for(i=0;i<=12;i++)
{
for(j=0;j<=12;j++)
cout<<maze[i][j]<<endl;
}
}
编译之后提示有三个警告，但是多编译几次的话，就会没有错误和警告。然而执行的时候，就会遇到错误弹出窗口！不晓得哪里有问题了！求哪位高手帮个忙，或者我加你QQ，我还有很多不懂的地方想请教！谢谢...