📄 迷宫问题.cpp
字号:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char MazeType;
#define SIZE 100 //存储空间初始分配量
MazeType maze[10][17]={
{"0001111111111111"},
{"1000001100010101"},
{"1011001100010101"},
{"1000010000010101"},
{"1000001100010101"},
{"1000001111010101"},
{"100000110001O1O1"},
{"1000001100110101"},
{"1000001100000001"},
{"1111111111110111"},
};
typedef struct{ //迷宫中r行c列的位置
int r;
int c;
}PostType;
typedef struct
{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct
{
SElemType elem[SIZE];
int top;
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.top=-1;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==-1)
return TRUE;
else
return ERROR;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top==SIZE-1)//栈满
exit(OVERFLOW); //存储分配失败
S.top++;
S.elem[S.top].di=e.di;
S.elem[S.top].seat.r=e.seat.r;
S.elem[S.top].seat.c=e.seat.c;
S.elem[S.top].ord=e.ord;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==-1)
return ERROR;
e.ord=S.elem[S.top].ord;
e.di=S.elem[S.top].di;
e.seat.r=S.elem[S.top].seat.r;
e.seat.c=S.elem[S.top].seat.c;
return OK;
}//Pop
Status Pass(MazeType maze[10][17],PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze[curpos.r][curpos.c]=='0')//可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType maze[10][17],PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze[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[10][17],PostType curpos){
//曾走过但不是通路标记并返回OK
maze[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//MarkPrint
Status MazePath(MazeType maze[10][17],PostType start,PostType end){
//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
//并返回TRUE,否则返回FALSE
Stack S;
PostType curpos;
int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e;
InitStack(S);
curpos.c=start.c;
curpos.r=start.r;//设置"当前位置"为"入口位置"
curstep=1; //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,即是未曾走到过的通道
FootPrint(maze,curpos);//留下足迹
e.ord=curstep;
e.seat.c=curpos.c;
e.seat.r=curpos.r;
e.di=1;
Push(S,e); //加入路径
if(curpos.r==end.r&& curpos.c==end.c)
return TRUE; //到达出口
else{
curpos=NextPos(curpos,e.di); //下一位置是当前位置的东邻
curstep++; //探索下一步
}//else
}//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 < 5){
e.di++;//换下一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是该
//新方向上的相邻
}//if
}//if
}//else
}while(!StackEmpty(S));
return TRUE;
}//MazePath
void PrintMaze(MazeType maze[10][17]){
//将标记路径信息的迷宫输出到终端(包括外墙)
int i,j;
printf("\nShow maze path(*---pathway):\n\n");
printf(" ");
for(i=0;i<=16;i++)//打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=9;i++){
printf("%2d",i);//打印行名
for(j=0;j<=16;j++)
printf("%4c",maze[i][j]);//输出迷宫//当前位置的标记
printf("\n\n");
}
}//PrintMaze
Status InitStack(Stack *S);
void main(){ //主函数
PostType start,end;
printf("-------FOUND A MAZEPATH--------\n");
PrintMaze(maze);
do{ //输入迷宫入口坐标
printf("\nEnter entrance coordinate of the maze: ");
scanf("%d%d",&start.r,&start.c);
if(start.r>10 || start.c>16){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(start.r>10|| start.c>16);
do{ //输入迷宫出口坐标
printf("\nEnter exit coordinate of the maze: ");
scanf("%d%d",&end.r,&end.c);
if(end.r>10 || end.c>16){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(end.r>10|| end.c>16);
MazePath(maze,start,end);
PrintMaze(maze);//打印路径
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -