迷宫求解原码

1、迷宫求解原码 （ 带详细注释 ）#include <stdio.h>#include <stdlib.h> #define TRUE 1#define FALSE 0#define NULL 0#define OK 1#define ERROR 0#define STATUS int#define SIT '' /#define SIN '-' /用于记录可以通过的通道块 用于记录走过 , 但不能通过的通道块#define FG(t,c) int t=0; for(;t < 80;t+)printf("%c",c

2、); /用于输出分隔条typedef struct /定义一个点int x; /点的 x 坐标int y; /点的 y 坐标char r; /记录该点是否可走的字符，若可走为'Y',不可走为'N'Point,*PPoint; /定义点的数据类型和指针类型typedef struct / int ord; /Point point; / int di; /定义走过的一段路当前所走的路径的序号当前坐标的点走向下一地点的方向SEletype,*PSEletype;typedef struct / 定义堆栈PSEletype bp,sp; / int size;/int

3、 length;/Stack;typedef struct /PPoint p; /int h;/int v;/Maze;栈底指针 , 栈顶指针 记录现在的容量 记录现在的长度定义一个迷宫迷宫元素的头指针迷宫的行数迷宫的列数定义栈初始容量定义栈满时的增初始化堆栈将一个元素压入 判断堆栈是否为 从堆栈中弹出一 查看堆栈中所有 读入迷宫的数据查看一个迷宫/使用默认迷宫const int STACK_INCRIMENT=10; / const int STACK_INITLENGTH=10; / 加容量int initStack(Stack& stack); /STATUS push(Sta

4、ck& stack,SEletype ip); / 堆栈STATUS stackEmpty(Stack& stack); / 空STATUS pop(Stack& stack,SEletype &e); / 个元素赋值给 evoid viewStack(Stack& stack); / 的元素void inputMaze(Maze& maze);/void viewMaze(Maze& maze);/void getPoint(Maze& maze,Point &start,Point &end); 读入起始位置和

5、结束位置void defaultMaze(Maze& maze); /void FootPrintY(Point* curp);/的足迹void FootPrintN(Point* curp);/留下走过可通过留下走过不能通过的足迹Point* nextPos(Maze &maze,Point* current,int direction); / 返回下点的相邻邻接块STATUS MazePath(Maze& maze,Point &start,Point &end,Stack &stack); / 求解迷宫的路径 STATUSpass(Poin

6、t* p); / 可能通过STATUS pointEqul(Point* p1,Point* p2); / void CopyPoint(Point &point,Point* pointc); int getMenuResult(); / 返回用户选择的功能号 void Mainaction(); void showLeaveMessage(int i); 息 void destroyMaze(Maze &maze);/判断当前位置是否/判断两个是否相等 拷贝一个点 显示提示菜单 , 并主要操作流程 显示系统退出信消毁迷宫void main()Mainaction();/主函

7、数/STATUS initStack(Stack& stack) if(!(stack.bp=(PSEletype)malloc(sizeof(SEletype)*STACK_INITLENGTH)return NULL;初始化堆栈stack.sp=stack.bp;stack.length=0;将一个元素如果堆栈未满 ,如果堆栈stack.size=STACK_INITLENGTH;return OK;STATUS push(Stack& stack,SEletype ip) / 压入堆栈if(stack.length < stack.size) / 直接赋值(stac

8、k.sp)->di=ip.di; stack.sp->ord=ip.ord;(stack.sp+)->point=ip.point; stack.length+;/printf("Input:%d,%dn",ip.di,ip.ord); return OK;else /满 , 则另外分配空间if(!(stack.bp=(PSEletype)realloc(stack.bp,(stack.size+STACK_INCRIMENT)*sizeof(SEletype)return NULL; /printf("Test:%d,%dn",ip.

9、di,ip.ord); stack.sp=stack.bp+stack.length; stack.sp->di=ip.di; stack.sp->ord=ip.ord; (stack.sp+)->point=ip.point; stack.length+;return OK;从堆栈中若栈空 ,若栈不为判断堆查看堆栈中所STATUSpop(Stack& stack,SEletype &e) / 弹出一个元素赋值给 eif(stackEmpty(stack) / 返回错误信息return ERROR;e.di=(-stack.sp)->di;/空, 则读入

10、到 e 中e.ord=stack.sp->ord;e.point=stack.sp->point;/printf("Pop:%d",stack.sp->di);stack.length-;return OK;STATUS stackEmpty(Stack& stack)/栈是否为空return stack.length=0?TRUE:FALSE;void viewStack(Stack& stack) / 有的元素PSEletype temp=stack.bp;int i=0;while(temp < stack.sp)i+;prin

11、tf("->(%d,%d)",temp->point.x,(temp+)->point.y); if(i %6 = 0)printf("n");printf("n");void inputMaze(Maze& maze) / 读入迷宫的数 据int h=0,v=0; / 读入迷宫的行 数和列数int i,j;printf(" 输入迷宫的行数 :"); scanf("%d",&h);printf(" 输入迷宫的列数 :"); scanf(&qu

12、ot;%d",&v);maze.p=(PPoint)malloc(sizeof(Point)*(h+2)*(v+2); / 分 配 (h+2)*(v+2) 的空间存放迷宫maze.h=h+2;maze.v=v+2;printf(" 输入迷宫 若此点可走输入 Y|y, 不可走任意输入 , 不用空 格分隔 , 每行输入完成后请按回车 :n");for(i=0 ; i < maze.h ; i+)/ 使用循环读入flushall(); / 清空每行的缓存for(j=0; j < maze.v ;j+ )if(i = 0 | i = maze.h-1

13、| j = 0 | j = maze.v-1) (maze.p+(i*maze.v)+j)->r='N' / 将迷宫四周用 'N' 封闭else scanf("%c",&(maze.p+(i*maze.v)+j)->r); / 读 入数据到迷宫if( (maze.p+(i*maze.v)+j)->r = 'Y' |(maze.p+(i*maze.v)+j)->r = 'y')(maze.p+(i*maze.v)+j)->r = 'Y'else (maze.p

14、+(i*maze.v)+j)->r = 'N'(maze.p+(i*maze.v)+j)->x=i;(maze.p+(i*maze.v)+j)->y=j;void viewMaze(Maze& maze) / 查看一个迷宫int i,j;for(i=0; i < maze.h ; i+)for(j=0; j < maze.v ; j+)printf("%c ",(maze.p+(i*maze.v)+j)->r); printf("n");void getPoint(Maze &maze,

15、Point &start ,Point &end) /读入起始位置和结束位置int h,v;printf(" 输入起始点的坐标 , 如(2,3): 你可输入的范围是 (1,1)-(%d,%d):",maze.h-2,maze.v-2);flushall();scanf("(%d,%d)",&h,&v);while(!(h >=1 && h <= maze.h-2) && (v >= 1 && v <= maze.v-2)printf(" 输入

16、错误 , 请再次输入起始点的坐标 , 如(2,3): 你可 输入的范围是 (1,1)-(%d,%d):",maze.h-2,maze.v-2);flushall(); scanf("(%d,%d)",&h,&v);start.x=h;start.y=v;flushall();printf(" 输入结束点的坐标 , 如(2,3): 你可输入的范围是 (1,1)-(%d,%d):",maze.h-2,maze.v-2);scanf("(%d,%d)",&h,&v);while(!(h >=1

17、 && h <= maze.h-2) && (v >= 1 && v <= maze.v-2)printf(" 输入错误 , 请再次输入结束点的坐标 , 如 (2,3): 你可 输入的范围是 (1,1)-(%d,%d):",maze.h-2,maze.v-2);flushall();scanf("(%d,%d)",&h,&v);end.x=h;end.y=v;flushall();/printf(" 读入出境的坐标分别为:d,%d,%d,%d",star

18、t.x,start.y,e nd.x,e nd.y);void defaultMaze(Maze& maze) / 使用默认迷宫int i,j;char t88='Y','Y','N','Y','Y','Y','N','Y','Y','Y','N','Y','Y','Y','N','Y','Y','Y'

19、,'Y','Y','N','N','Y','Y','Y','N','N','N','Y','Y','Y','Y','Y','Y','Y','N','Y','Y','Y','Y','Y','N','Y'

20、,'Y','Y','N','Y','Y','Y','N','N','N','Y','N','N','Y','N','Y','Y','Y','Y','Y','Y','Y'maze.h=maze.v=10;maze.p=(PPoint)malloc(sizeof(Po

21、int)*(10)*(10);使用循for(i=0 ; i < maze.h ; i+)/环读入for(j=0; j < maze.v ;j+ )if(i = 0 | i = maze.h-1| j = 0 | j = maze.v-1)(maze.p+(i*maze.v)+j)->r='N' / 将迷宫四周用 'N' 封闭else(maze.p+(i*maze.v)+j)->r=ti-1j-1; / 将矩阵 的值赋值给迷宫(maze.p+(i*maze.v)+j)->x=i;(maze.p+(i*maze.v)+j)->y=

22、j;void FootPrintY(Point* curp) / 留下走过可能通过的足迹/printf("(%d,%d) 被标记通过 n",curp->x,curp->y); curp->r=SIT;void FootPrintN(Point* curp) / 留下走过不通过的足迹/ printf("(%d,%d) 被标记不能走过 n",curp->x,curp->y); curp->r=SIN;Point* nextPos(Maze &maze,Point* current,int direction)/ 返

23、回下点的相邻邻接块Point *p; if(direction = 1) / p=current+1;else if(direction = 2) /p=current+maze.v;else if(direction = 3) / p=current-1;else /p=current-maze.v;/printf("return p;找出右边的点找出下边的点找出左边的点找出上边的点找到的下一个节点是:(%d,%d)n",p->x,p->y);STATUS pass(Point* p) / 判断当前位置是否可能通过return p->r='Y&#

24、39;?TRUE:FALSE;STATUS MazePath(Maze& maze ,Point &start,Point &end,Stack&stack) / 求解迷宫的路径SEletype se; initStack(stack);PPoint po;计算出堆栈中的记录当前走过的如果该通道块可po=maze.p+maze.v*(start.x)+start.y; /起始点int curstep=1; / 通道块的次数doif(pass(po) / 以通过/printf("(%d,%d,%c) 可以通过n",po->x,po->

25、;y,po->r);FootPrintY(po);/向可以通过的通道块做标记CopyPoint(se.point,po);/把当前点拷贝到se 中, 用于在栈中保存路径se.ord=curstep;/记录当前的通道块数目se.di=1; /下一次的方向 (1表示向右 )push(stack,se);/保存 se, 记录走过的路径if(pointEqul(po,&end)/如果当前的点是通道的出口则返回有路可走若当前的点不是return TRUE;po=nextPos(maze,po,1); /通道的出口 , 寻找该点右边的点curstep+;else/printf("(

26、%d,%d,%c) 不可以通过n",po->x,po->y,po->r);if(!stackEmpty(stack) / 如果当前通道块 不能走过 , 且堆栈不为空PPoint p;pop(stack,se); / 向后退一个通道块 p=maze.p+(se.point.x*maze.v)+se.point.y; / 根据堆栈中刚弹出的 se 求出后一个坐标的位置/printf("(%d,%d,%c) 从栈中弹出:n",p->x,p->y,p->r);while(se.di = 4 && !stackEmpty(

27、stack) /如果新弹出的通道块是上一个方向上最后一个通道块/在堆栈不为空的前提下 , 弹出所有的最后通道块 , 直到找到下一个可 走的路径 , 并对不能通过的点做下标记p=maze.p+(se.point.x*maze.v)+se.point.y;/ 根据堆栈中刚弹出的 se 求出后一个坐标的位置FootPrintN(p);/留下不能通过的标记pop(stack,se);/弹出 di 为 4 的路径点if(se.di < 4) /如果 di<4, 说明有下一个可走的路径se.di+;push(stack,se);/将当前点放入堆栈/po=nextPos(maze,p,se.di

28、);计算下一个要走过的点while(!stackEmpty(stack);return FALSE;STATUS pointEqul(Point *p1,Point *p2) / 判断两个是否相等 if( (p1->x = p2->x) && (p1->y = p2->y) return TRUE;return FALSE; void CopyPoint(Point &point,Point* pointc) / 拷贝一个点 point.x=pointc->x;point.y=pointc->y;int getMenuResult()

29、择的功能号printf("nttt*/显示提示菜单 , 并返回用户选*");printf("nttt$ WALK Maze $"); printf("nttt*");printf("nttt| 1.Use default Maze|");printf("nttt| 2.Create customer Maze |");printf("nttt| 3.Look up Maze message |");printf("nttt| 4.Walk along the Maz

30、e |");printf("nttt| 0.Exit system |");printf("nttt*");printf("nttt->Input your choice:"); int temp;flushall();scanf("%d",&temp);return temp;void Mainaction() / 主要操作流程Maze maze;maze.p=NULL;int ct=0;ct=getMenuResult();for(;)if(ct = 1) / 如果选择为 1,则 建立默

31、认迷宫maze.p=NULL; defaultMaze(maze); FG(i,'-') printf("ntttDefault Maze has created!n"); FG(j,'-')else if(ct = 2) / 如果选择为 2, 则用 户输入迷宫FG(i,'-'); maze.p=NULL;inputMaze(maze);printf("ntttCustomer Maze has created!n");FG(j,'-')else if(ct = 3)FG(i,'-');if(maze.p = NULL)printf("tttMaze don't exit,please create theMaze!n");elseprintf("ntttMaze message!n");viewMaze(maze);FG