迷宫求解细节

1、一、 需求分析1.选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。 2.基本原理分析 迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路

2、都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。 3.功能要求 （1）以一个二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0<=j<=n+1)及Mazei0和Mazein+1 (0<=i<=m+1)为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n<=10。（2）用户需用文

3、件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，“”表示曾途经该位置但不能到达出口，其余位置用空格符表示。若设定迷宫不存在通路则报告相应信息（5）本程序只求出一条成功的通路。（6）程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。二、 详细设计源程序:#include <stdio.h>#inc

4、lude <stdlib.h>#include <string.h>#define MAXLEN 10/迷宫包括外墙最大行列数目#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 typedef int Status;/ 坐标位置类型 typedef struct    int r,c; PosType;/迷宫中r行c列的位置/迷宫类型 typedef struct      int r;  

5、;   int c;     char arrMAXLENMAXLEN;/可取' ','*','','#'MazeType;    typedef struct/int step; / 当前位置在路径上的“序号”   PosType seat; /当前的坐标位置   int di; /往下一坐标位置的方向SElemType; /结点类型typedef struct NodeType 

6、  SElemType data;   NodeType *next;NodeType,*LinkType;/栈类型 typedef struct    LinkType top;   int stacksize;SqStack;  PosType start;PosType end;MazeType maze;bool found; /创建栈Status InitStack(SqStack &S)   S.top=(LinkType)malloc(sizeof(No

7、deType);   S.top->next=NULL;   S.stacksize=0;   return OK; /进栈Status Push(SqStack &S,SElemType &e)   LinkType p;   p=(NodeType*)malloc(sizeof(NodeType);   p->data=e;   p->next=S.top;   S.top=p; 

8、;  S.stacksize+;   return OK; /判断是否为栈空Status StackEmpty(SqStack S)   if(S.top->next=NULL) return OK;   return ERROR;  /出栈Status Pop(SqStack &S,SElemType &e)   LinkType p;   if(StackEmpty(S) return ERROR;   p=S.top;

9、   e=p->data;   S.top=S.top->next;   S.stacksize-;   free(p);   return OK; /销毁栈Status DestroyStack(SqStack &S)   LinkType p;   while(S.top!=NULL)         p=S.top;   

10、   S.top=S.top->next;      free(p);   /一个一个删除   if(S.top=NULL) return OK;   else return ERROR; /曾走过但不是通路标记并返回OKStatus MarkPrint(MazeType &maze,PosType curpos) maze.arrcurpos.rcurpos.c=''/""表示曾走过但不通

11、60;return OK; /曾走过而且是通路标记并返回OKStatus FootPrint(MazeType &maze,PosType curpos)  maze.arrcurpos.rcurpos.c='*'/"*"表示可通  return OK; /选择下一步的方向PosType NextPos(PosType &curpos,int i)   PosType cpos;   cpos=curpos;   switch(i) 

12、       /1.2.3.4分别表示东,南,西,北方向      case 1 : cpos.c+=1;           break;      case 2 : cpos.r+=1;           break;    

13、0; case 3 : cpos.c-=1;           break;      case 4 : cpos.r-=1;           break;return cpos; /判断当前位置是否可通 Status Pass(MazeType &maze, PosType curpos)    if(maze.arrcurpos.

14、rcurpos.c=' ') return TRUE;      else return FALSE; /创建迷宫/按照用户输入的二维数组（0或1），设置迷宫maze的初值，包括加上边缘一圈的值void InitMaze(MazeType &maze, char aMAXLENMAXLEN, int row, int col)   maze.r=row;   maze.c=col;   for(int i=0;i<=col+1;i+) 

15、      a0i='1'       arow+1i='1'      for(i=0;i<=row+1;i+)       ai0='1'       aicol+1='1'      for(i=0;i<=maze.r+2;i+) 

16、60;    for(int j=0;j<maze.c+2;j+)        if(aij='1') maze.arrij='#'        else maze.arrij=' '          /求迷宫路径的伪码算法：Status MazePath(MazeType &maze,Po

17、sType start,PosType end)/求解迷宫maze中，从入口start到出口end的一条路径，若存在，返回TRUE,否则返回FALSE   PosType curpos;   SqStack S;   SElemType e;   InitStack(S);   curpos=start;/设定“当前位置”为“入口位置”  /curstep=1; /探索第一步   found=false;do   if(Pass(maze,cur

18、pos)       /当前位置可以通过，即是未曾走到过的通道块留下足迹   FootPrint(maze,curpos);/做可以通过的标识/e.step=curstep;   e.seat=curpos;     e.di=1;          /为栈顶元素赋值    Push(S,e); /加入路径   if(curpo

19、s.r=end.r && curpos.c=end.c) found=true;/如果到达终点返回true     else          curpos=NextPos(curpos,1);/下一位置是当前位置的东邻           else   /当前位置不能通过     if(!StackEmpty(S)

20、60;        Pop(S,e);         while(e.di=4 && !StackEmpty(S)            MarkPrint(maze,e.seat);  /留下不能通过的标记        

21、60;   Pop(S,e);                 if(e.di<4)          e.di+;   /换下个方向          Push(S,e);    &

22、#160;                  /          curpos=NextPos(e.seat,e.di);     /进行探索               whi

23、le(!StackEmpty(S)&&!found);DestroyStack(S);return found; /将标记路径信息的迷宫（字符型方阵）输出到终端(包括外墙)void PrintMaze(MazeType &maze)    for(int i=0;i<=maze.r+2;i+)      for(int j=0;j<=maze.c+2;j+)  printf("  %c",maze.arrij);/输出迷宫

24、0;                  printf("n");     /系统初始化void Initialization()system("cls"); printf("     welcome to the game!       "); printf(

25、"n*");printf("n*创建迷宫-c 执行迷宫-m 输出迷宫-p  退出-q*");printf("n*");printf("nn    操作:-"); /读入操作命令符，显示提示信息void ReadCommand(char &cmd) do   if(cmd='c')       printf("n*"); &#

26、160;  printf("n*选择操作 :执行迷宫-m     *");    printf("n* 退出-:q           *");    printf("n*");    printf("nn  操作:-");    

27、0; else if(cmd='m')    printf("n*");    printf("n*选择操作 :输出迷宫-p          *");    printf("n* 退出-:q        *");    printf(&qu

28、ot;n*");    printf("nn 操作:-");       else if(cmd='p')    printf("n*");    printf("n*选择操作 :执行迷宫-c          *");    printf("

29、n*          退出-:q       *");    printf("n*");    printf("nn          操作:-");     cmd=getchar();while(!(cmd=

30、9;c'|cmd='m'|cmd='p'|cmd='q'); /解释cmd-具体执行void Interpre(char cmd)switch(cmd)case 'c':   int rnum, cnum, i=0,m=1,n=1;   char a2MAXLENMAXLEN;   char input1;   char data1000;   printf("n请输入迷宫数据文件名！n");&

31、#160;  scanf("%s",input);   FILE *fp;   fp=fopen(input,"r");   if(!fp)       printf("n不能打开文件n");     break;    while(!feof(fp)       fscanf(fp,"%s",&a

32、mp;datai);    if(i=0)            rnum=(int)datai-(int)'0'        if(i=1)            cnum=(int)datai-(int)'0'      

33、  if(i>=2)         if(n>cnum)m+;n=1;     a2mn=datai;     n+;        i+;      fclose(fp);InitMaze(maze, a2, rnum, cnum);   printf("n迷宫建立完成！n");&#

34、160;  break;    case 'm':   printf("n请输入迷宫入口的坐标，以空格为间隔:-");   scanf("%d %d",&start.r,&start.c);   printf("n请输入迷宫出口的坐标，以空格为间隔:-");   scanf("%d %d",&end.r,&end.c);   MazePath(maze, start, end);   break;    case 'p':