迷宮求解細(xì)節(jié)

1、一、 需求分析1.選題理由本次課設(shè)我選擇了迷宮問題，迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個經(jīng)典問題，迷宮問題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng)用“棧”的思想。對于棧的內(nèi)容在整個學(xué)期的學(xué)習(xí)中我也有了一定的了解，所以選擇了迷宮這一經(jīng)典問題作為本次課設(shè)的內(nèi)容。 2.基本原理分析 迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路

2、都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。棧是一個后進(jìn)先出的結(jié)構(gòu)，可以用來保存從入口到當(dāng)前位置的路徑。以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何一個位置，均約定東、南、西、北四個方向可通。 3.功能要求 （1）以一個二維數(shù)組Mazem+2n+2表示迷宮，其中：Maze0j和Mazem+1j(0<=j<=n+1)及Mazei0和Mazein+1 (0<=i<=m+1)為做外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為：m,n<=10。（2）用戶需用文

3、件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第2行至第m+1行（每行n個數(shù)）為迷宮值，用0，1輸入，同行中的兩個數(shù)字之間用空白字符相隔。（3）迷宮的入口位置和出口位置可由用戶隨時設(shè)定。（4）若設(shè)定的迷宮存在通路，則以長方陣形式將迷宮及其通路輸出到標(biāo)準(zhǔn)輸出文件上，其中字符“#”表示障礙，“*”表示路徑，“”表示曾途經(jīng)該位置但不能到達(dá)出口，其余位置用空格符表示。若設(shè)定迷宮不存在通路則報告相應(yīng)信息（5）本程序只求出一條成功的通路。（6）程序執(zhí)行的命令為：1，創(chuàng)建迷宮；2，求解迷宮；3，輸出迷宮的解。二、 詳細(xì)設(shè)計源程序:#include <stdio.h>#inc

4、lude <stdlib.h>#include <string.h>#define MAXLEN 10/迷宮包括外墻最大行列數(shù)目#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 typedef int Status;/ 坐標(biāo)位置類型 typedef struct    int r,c; PosType;/迷宮中r行c列的位置/迷宮類型 typedef struct      int r;  

5、;   int c;     char arrMAXLENMAXLEN;/可取' ','*','','#'MazeType;    typedef struct/int step; / 當(dāng)前位置在路徑上的“序號”   PosType seat; /當(dāng)前的坐標(biāo)位置   int di; /往下一坐標(biāo)位置的方向SElemType; /結(jié)點(diǎn)類型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; /創(chuàng)建棧Status InitStack(SqStack &S)   S.top=(LinkType)malloc(sizeof(No

7、deType);   S.top->next=NULL;   S.stacksize=0;   return OK; /進(jìn)棧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; /曾走過但不是通路標(biāo)記并返回OKStatus MarkPrint(MazeType &maze,PosType curpos) maze.arrcurpos.rcurpos.c=''/""表示曾走過但不通

11、60;return OK; /曾走過而且是通路標(biāo)記并返回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; /判斷當(dāng)前位置是否可通 Status Pass(MazeType &maze, PosType curpos)    if(maze.arrcurpos.

14、rcurpos.c=' ') return TRUE;      else return FALSE; /創(chuàng)建迷宮/按照用戶輸入的二維數(shù)組（0或1），設(shè)置迷宮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;/設(shè)定“當(dāng)前位置”為“入口位置”  /curstep=1; /探索第一步   found=false;do   if(Pass(maze,cur

18、pos)       /當(dāng)前位置可以通過，即是未曾走到過的通道塊留下足跡   FootPrint(maze,curpos);/做可以通過的標(biāo)識/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;/如果到達(dá)終點(diǎn)返回true     else          curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰           else   /當(dāng)前位置不能通過     if(!StackEmpty(S)

20、60;        Pop(S,e);         while(e.di=4 && !StackEmpty(S)            MarkPrint(maze,e.seat);  /留下不能通過的標(biāo)記        

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

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

23、le(!StackEmpty(S)&&!found);DestroyStack(S);return found; /將標(biāo)記路徑信息的迷宮（字符型方陣）輸出到終端(包括外墻)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");     /系統(tǒng)初始化void Initialization()system("cls"); printf("     welcome to the game!       "); printf(

25、"n*");printf("n*創(chuàng)建迷宮-c 執(zhí)行迷宮-m 輸出迷宮-p  退出-q*");printf("n*");printf("nn    操作:-"); /讀入操作命令符，顯示提示信息void ReadCommand(char &cmd) do   if(cmd='c')       printf("n*"); &#

26、160;  printf("n*選擇操作 :執(zhí)行迷宮-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*選擇操作 :執(zhí)行迷宮-c          *");    printf("

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

30、9;c'|cmd='m'|cmd='p'|cmd='q'); /解釋cmd-具體執(zhí)行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請輸入迷宮數(shù)據(jù)文件名！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請輸入迷宮入口的坐標(biāo)，以空格為間隔:-");   scanf("%d %d",&start.r,&start.c);   printf("n請輸入迷宮出口的坐標(biāo)，以空格為間隔:-");   scanf("%d %d",&end.r,&end.c);   MazePath(maze, start, end);   break;    case 'p':