//base.h
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//stack.h
#define STACK_INIT_SIZE 100 //存储空间初始量
#define STACK_INCREMENT 10//存储空间初始增量
typedef struct
{
int r;
int c;
}PostType;//坐标位置 迷宫的r行c列
typedef struct
{
int ord;//通道块在路径上的序号
PostType seat;//通道块的当前坐标位置
int di;//通道块指向下一通道块的方向
}SElemType;//栈元素的类型
typedef struct
{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈的最大容量
}Stack;//栈的类型
Status InitStack(Stack &S)//初始化栈
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S)
//判断栈是否为空,如果为空返回TRUE,否则返回FALSE
{
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e)
//插入元素为e的栈顶元素
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*S.top++=e;
return OK;
}//Push
Status Pop(Stack &S,SElemType &e)
//删除栈顶元素存入e
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S)
//销毁栈
{
free(S.base);
S.top=S.base;
return OK;
}//DestroyStack
//maze.cpp
#define MAXLEN 20//迷宫包括外墙最大行列数目
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j,k=1;
printf("输入迷口的行数和列数: ");
scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
for(i=0;i<=maze.c+1;i++){//迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++){//迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宫
printf("输入障碍物%d的坐标(以坐标(0,0)结束输入): ",k);
scanf("%d%d",&m,&n);//接收障碍的坐标
k++;
while(m!=0)
{
if(m>maze.r || n>maze.c)//越界
exit(ERROR);
maze.adr[m][n]='#';//迷宫障碍用'#'标记
printf("输入障碍物%d的坐标(以坐标(0,0)结束输入): ",k);
scanf("%d%d",&m,&n);
k++;
}
return OK;
}//InitMaze
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//MarkPrint
void PrintMaze(MazeType &maze)
//将最后标记好的迷宫输出
{
int i,j;
printf("\n输出迷宫的路径:\n");
for(i=0;i<=maze.c+1;i++)
printf("%4d",i);//输出列数
printf("\n");
for(i=0;i<=maze.r+1;i++)
{
printf("%d",i);//输出行数
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);//输出迷宫
printf("\n");
}
}//PrintMaze
Status MazePath(MazeType &maze,PostType start,PostType end)
//若迷宫从入口start到end的通道则求得一条存放在栈中
{
Stack S;//初始化栈
PostType curpos;
int curstep;
SElemType e;
InitStack(S);
curpos=start;
curstep=1;
do
{
if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹
{
FootPrint(maze,curpos);
e.ord=curstep;e.seat=curpos;e.di=1;
Push(S,e);//加入栈路径中
if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE
{
if(!DestroyStack(S))
exit(OVERFLOW);
else return TRUE;
}
else
{
curpos=NextPos(curpos,1);//下一位置是当前位置
curstep++;//探索下一步
}
}//if
else//当前位置不能通过
{
if(!StackEmpty(S))
{
Pop(S,e);//提取前一位置
while (e.di==4 && !StackEmpty(S))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过
{
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di<4)//换下一个方向探索 设定当前位置为该新方向上的邻位
{
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}
}//if
}
}while(!StackEmpty(S));
if(!DestroyStack(S))
exit(ERROR);
else return FALSE;
}//MazePath
void main()
{
MazeType maze;
PostType start,end;
char c;
do
{
printf("----------找一条迷宫的路径-------------\n");
if(!InitMaze(maze))
{
printf("\n 初始化迷宫失败!!!");
exit(ERROR);
}
do
{
printf("\n请输入入口的坐标:");
scanf("%d%d",&start.r,&start.c);//输入入口坐标
if(start.r>maze.r || start.c>maze.c)
printf("\n输入错误,请重新输入入口的坐标!!\n");
continue;
}
while (start.r>maze.r || start.c>maze.c);
do
{
printf("\n请输入出口的坐标:");//输入出口的坐标
scanf("%d%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c)
printf("\n输入错误,请重新输入出口坐标!!\n");
continue;
}
while (end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf("\n不能找到一条路径!!!\n");
else PrintMaze(maze);//输出迷宫
printf("是否要继续?(y/n):");
scanf("%s",&c);
}
while (c=='y' || c=='Y');
}//main