《用c语言实现迷宫求解完美源代码.doc》由会员分享，可在线阅读，更多相关《用c语言实现迷宫求解完美源代码.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define UNDERFLOW -2typedef int Status;/-栈开始-typedef struct/迷宫中r行c列的位置int r;int c;PostType;/坐标位置类型typedef structint ord;/ 当前位置在路径上的序号PostType seat;/ 当前坐标int di;/ 从此通块走向下一通块的“
2、方向”SElemType;/ 栈的元素类型/定义链式栈的存储结构struct LNodeSElemType data;/数据域struct LNode *next;/指针域struct LStackstruct LNode *top;/栈顶指针Status InitStack(LStack &s)/操作结果：构造一个空栈Sstruct LNode *p; p=(LNode *)malloc(sizeof(LNode);if(!p)printf(分配失败，退出程序); exit(ERROR);s.top=p;p-next=NULL;return OK;Status StackEmpty(LSta
3、ck s) /若栈s为空栈，则返回TRUE，否则FALSEif(s.top-next=NULL) return TRUE;return FALSE; Status Push(LStack &s,SElemType e)/插入元素e成为新的栈顶元素struct LNode *p;p=(LNode *)malloc(sizeof(LNode);if(!p) exit(OVERFLOW);s.top-data=e;p-next=s.top; s.top=p;return OK;Status Pop(LStack &s,SElemType &e)/删除s的栈顶元素，并且用e返回其值struct LNo
4、de *p;if(!(s.top-next) exit(UNDERFLOW);p=s.top; s.top=p-next;e=s.top-data;free(p); return OK;Status DestroyStack(LStack &s)/操作结果：栈s被销毁struct LNode *p;p=s.top; while(p)s.top=p-next;free(p);p=s.top; return OK;/-栈结束-/-迷宫开始-#define MAXLEN 10/ 迷宫包括外墙最大行列数typedef structint r;int c;char adrMAXLENMAXLEN;/ 可
5、取 * #MazeType;/ 迷宫类型Status InitMaze(MazeType&maze)/ 初始化迷宫，成功返回TRUE，否则返回FALSEint m,n,i,j;printf(输入迷宫行数和列数（包括了外墙）: );scanf(%d%d,&maze.r,&maze.c); / 输入迷宫行数和列数for(i=0;i=maze.c+1;i+)/ 迷宫行外墙maze.adr0i=#;maze.adrmaze.r+1i=#;/forfor(i=0;i=maze.r+1;i+)/ 迷宫列外墙maze.adri0=#;maze.adrimaze.c+1=#;for(i=1;i=maze.r;
6、i+)for(j=1;jmaze.r | nmaze.c)/ 越界exit(ERROR);maze.adrmn=#;/ 迷宫障碍用#标记printf(输入障碍的坐标(-1,-1)结束): );scanf(%d%d,&m,&n);/whilereturn OK;/InitMazeStatus Pass(MazeType maze,PostType curpos)/ 当前位置可同则返回TURE,否则返回FALSEif(maze.adrcurpos.rcurpos.c= )/ 可通return TRUE;elsereturn FALSE;/PassStatus FootPrint(MazeType
7、&maze,PostType curpos)/ 若走过并且可通，则返回TRUE,否则返回FALSEmaze.adrcurpos.rcurpos.c=*;/*表示可通return OK;/FootPrintPostType 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 : cpo
8、s.r-=1; break;default: exit(ERROR); return cpos;/NextposStatus MarkPrint(MazeType &maze,PostType curpos)/ 曾走过，但不是通路标记，并返回OKmaze.adrcurpos.rcurpos.c=;/ 表示曾走过但不通return OK;/MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end)/ 若迷宫maze存在通路，则求出一条同路放在栈中，并返回TRUE，否则返回FALSEstruct LStack S;Pos
9、tType curpos;int curstep;/ 当前序号，1,2,3,4分别表示东南西北方向SElemType e;InitStack(S);curpos=start; /设置当前位置为入口位置curstep=1;/ 探索第一位printf(以三元组形式表示迷宫路径：n);doif(Pass(maze,curpos)/ 当前位置可以通过FootPrint(maze,curpos);/ 留下足迹e.ord=curstep;e.seat=curpos;e.di=1;printf(%d %d %d-,e.seat.r,e.seat.c,e.di);Push(S,e);/ 加入路径if(curp
10、os.r=end.r&curpos.c=end.c)if(!DestroyStack(S)/ 销毁失败exit(OVERFLOW);elsereturn TRUE; / 到达出口elsecurpos=NextPos(curpos,1);/ 下一位置是当前位置的东邻curstep+;/ 探索下一步/else /ifelse/ 当前位置不通时 if(!StackEmpty(S)Pop(S,e);while(e.di=4& !StackEmpty(S)MarkPrint(maze,e.seat);Pop(S,e);/ 留下不能通过的标记，并退一步/whileif(e.di ,e.seat.r,e.s
11、eat.c,e.di);/if/if/elsewhile(!StackEmpty(S);if(!DestroyStack(S)/ 销毁栈exit(OVERFLOW);elsereturn FALSE;/MazePathvoid PrintMaze(MazeType &maze)/ 将标记路径信息的迷宫输出到终端int i,j;printf(n输出迷宫(*表示通路):nn);printf();for(i=0;i=maze.r+1;i+)/ 打印列数名printf(%4d,i);printf(nn);for(i=0;i=maze.r+1;i+)printf(%2d,i);/ 打印行名for(j=0
12、;jmaze.r |start.cmaze.c)printf(nBeyond the maze!n);continue;while(start.rmaze.r |start.cmaze.c);do/ 输入迷宫出口坐标printf(n输入迷宫出口坐标: );scanf(%d%d,&end.r,&end.c);if(end.rmaze.r |end.cmaze.c)printf(nBeyond the maze!n);continue; while(end.rmaze.r |end.cmaze.c);if(!MazePath(maze,start,end)/迷宫求解printf(nNo path from entranceto exit!n);elsePrintMaze(maze);/ 打印路径printf(n需要继续创建新的迷宫吗?(y/n): );scanf(%s,&cmd); while(cmd=y | cmd=Y);【精品文档】第 6 页