數(shù)據(jù)結(jié)構(gòu)迷宮求解算法

1、<p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#define overflow -1</p><p>　　#define ok 1</p><p>　　#define error 0</p><p>

2、　　#define STACK_INIT_SIZE 100</p><p>　　#define STACKINCREMENT 10</p><p>　　typedef int Status;</p><p>　　typedef struct </p><p><b>　　{</b></p><p&

3、gt;<b>　　int x;</b></p><p><b>　　int y;</b></p><p>　　}PosType;//位置類型</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　i

4、nt row,col;</p><p>　　int a[50][50];</p><p>　　}MazeType;//迷宮類型</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int ord;//通道塊在路徑上的序號(hào)</p>

5、<p>　　PosType seat;//通道塊在迷宮中的“坐標(biāo)位置”</p><p>　　int di;//從此通道塊走向下一個(gè)通道塊的方向</p><p>　　}SElemType;//棧的元素類型</p><p>　　typedef struct</p><p><b>　　{</b></p&g

6、t;<p>　　SElemType *base;</p><p>　　SElemType *top;</p><p>　　int Stacksize;</p><p>　　}SqStack;//棧結(jié)構(gòu)</p><p>　　Status InitStack(SqStack &S)//初始化棧</p><

7、;p><b>　　{</b></p><p>　　S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));</p><p>　　if(!S.base) exit (overflow);</p><p>　　S.top=S.base;</p><p&g

8、t;　　S.Stacksize=STACK_INIT_SIZE;</p><p>　　return ok;</p><p><b>　　}</b></p><p>　　Status Push(SqStack &S,SElemType e)//入棧</p><p><b>　　{</b><

9、;/p><p>　　if(S.top-S.base>=S.Stacksize)</p><p><b>　　{</b></p><p>　　S.base=(SElemType *)realloc(S.base,(S.Stacksize+STACKINCREMENT)*sizeof(SElemType));</p><p&g

10、t;　　if(!S.base) exit (overflow);</p><p>　　S.top=S.base+S.Stacksize;</p><p>　　S.Stacksize+=STACKINCREMENT;</p><p><b>　　}</b></p><p>　　*S.top++=e;</p>

11、<p>　　return ok;</p><p><b>　　}</b></p><p>　　Status Pop(SqStack &S,SElemType &e)//出棧</p><p><b>　　{</b></p><p>　　if(S.top==S.base) r

12、eturn error;</p><p>　　e=*--S.top;</p><p>　　return ok;</p><p><b>　　}</b></p><p>　　bool StackEmpty(SqStack S)//判斷棧是否為空</p><p><b>　　{</b&

13、gt;</p><p>　　if(S.top==S.base)</p><p>　　return ok;</p><p>　　else return error;</p><p><b>　　}</b></p><p>　　Status InitMaze(MazeType &maze)//

14、初始化迷宮</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for( j=0;j<maze.col+2;j++)</p><p>　　maze.a[0][j]=1;</p><p>　　for( i=1;

15、i<maze.row+1;i++)</p><p><b>　　{</b></p><p>　　maze.a[i][0]=1;</p><p>　　maze.a[i][maze.col+1]=1;</p><p>　　for(int j=1;j<maze.col+1;j++)</p><p

16、>　　scanf("%d",&maze.a[i][j]);</p><p><b>　　}</b></p><p>　　for(j=0;j<maze.col+2;j++)</p><p>　　maze.a[maze.row+1][j]=1;</p><p>　　return ok;

17、</p><p>　　}//為了避免檢查邊界，把迷宮的外圍都設(shè)成障礙，迷宮的內(nèi)核是row行，col列的數(shù)組</p><p>　　bool Pass(MazeType maze,PosType curpos)//判斷是否可以通過</p><p><b>　　{</b></p><p>　　return maze.a[cur

18、pos.x][curpos.y]==0;</p><p><b>　　}</b></p><p>　　Status FootPrint(MazeType &maze,PosType curpos)//留下足跡</p><p><b>　　{</b></p><p>　　maze.a[curp

19、os.x][curpos.y]=2;</p><p>　　return ok;</p><p><b>　　}</b></p><p>　　SElemType CreatElem(int step,PosType pos,int di)//創(chuàng)造一個(gè)SElemType型的數(shù)據(jù)</p><p><b>　　{<

20、;/b></p><p>　　SElemType e;</p><p>　　e.ord=step;</p><p>　　e.seat=pos;</p><p><b>　　e.di=di;</b></p><p><b>　　return e;</b></p>

21、;<p><b>　　}</b></p><p>　　bool IsEnd(PosType pos1,PosType pos2)//判斷是否結(jié)束</p><p><b>　　{</b></p><p>　　return pos1.x==pos2.x&&pos1.y==pos2.y;</p

22、><p><b>　　}</b></p><p>　　PosType NextPos(PosType curpos,int di)//向下一步搜索</p><p><b>　　{</b></p><p>　　PosType pos=curpos;</p><p>　　switch

23、(di)</p><p><b>　　{</b></p><p>　　case 1:pos.x++;break;//向東</p><p>　　case 2:pos.y++;break;//向南</p><p>　　case 3:pos.x--;break;//向西</p><p>　　case 4

24、:pos.y--;break;//向北</p><p><b>　　}</b></p><p>　　return pos;</p><p><b>　　}</b></p><p>　　Status MarkPrint(MazeType &maze,PosType curpos)//在死路處留

25、下印跡</p><p><b>　　{</b></p><p>　　maze.a[curpos.x][curpos.y]='*';</p><p>　　return ok;</p><p><b>　　}</b></p><p>　　Status MazePa

26、th(MazeType &maze,PosType start,PosType end)//尋找路徑</p><p><b>　　{</b></p><p>　　//若迷宮maze中存在從入口start到出口end的通道，則求得一條存放在棧中（從棧底到棧頂），</p><p>　　//并返回ture；否則返回false</p>

27、;<p>　　SqStack S;</p><p>　　SElemType e;</p><p>　　InitStack(S);</p><p>　　PosType curpos=start;//設(shè)定當(dāng)前位置為入口位置</p><p>　　int curstep=1;//探索第一步</p><p><

28、;b>　　do{</b></p><p>　　if(Pass(maze,curpos))</p><p><b>　　{</b></p><p>　　FootPrint(maze,curpos);//留下足跡</p><p>　　e=CreatElem(curstep,curpos,1);</p&

29、gt;<p>　　Push(S,e);//加入路徑</p><p>　　if(IsEnd(curpos,end))</p><p>　　return ok;//達(dá)到終點(diǎn)</p><p>　　curpos=NextPos(curpos,1);//下一步是當(dāng)期位置的東鄰</p><p>　　curstep++;//探索下一步<

30、/p><p><b>　　}</b></p><p>　　else//當(dāng)前位置不能通過</p><p><b>　　{</b></p><p>　　if(!StackEmpty(S))</p><p><b>　　{</b></p><p

31、><b>　　Pop(S,e);</b></p><p>　　while(e.di==4&&!StackEmpty(S))</p><p><b>　　{</b></p><p>　　MarkPrint(maze,e.seat);//留下不能通過的標(biāo)記，并退一步</p><p>

32、;<b>　　Pop(S,e);</b></p><p><b>　　}</b></p><p>　　if(e.di<4)</p><p><b>　　{</b></p><p>　　e.di++;//換下一個(gè)方向</p><p>　　Push(S

33、,e);</p><p>　　curpos=NextPos(e.seat,e.di);//設(shè)定當(dāng)前位置是新方向上的相鄰塊</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

34、t;　　}while(!StackEmpty(S));</p><p>　　return error;</p><p><b>　　}</b></p><p>　　Status PrintMaze(MazeType maze)//輸出迷宮</p><p><b>　　{</b></p>

35、<p><b>　　int i,j;</b></p><p>　　for(i=0;i<maze.row+2;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<maze.col+2;j++)</p><p>　　printf("

36、%d ",maze.a[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　return ok;</p><p><b>　　}</b></p><p>　　void mai

37、n()</p><p><b>　　{ </b></p><p>　　MazeType maze;</p><p>　　printf("請(qǐng)輸入迷宮的行數(shù)row和列數(shù)col：");</p><p>　　scanf("%d %d",&maze.row,&maze.

38、col);</p><p>　　printf("請(qǐng)輸入迷宮數(shù)據(jù)，0表示通道，1表示障礙：\n");</p><p>　　InitMaze(maze);</p><p>　　PosType start,end;</p><p>　　start.x=1;start.y=1;</p><p>　　end.

39、x=maze.row;end.y=maze.col;</p><p>　　if(MazePath(maze,start,end))</p><p><b>　　{</b></p><p>　　printf("迷宮走法（2代表走法，*代表不通）\n");</p><p>　　PrintMaze(maze