迷宮試驗(yàn)報(bào)告

本文格式為Word版，下載可任意編輯——迷宮試驗(yàn)報(bào)告一、試驗(yàn)內(nèi)容

3、迷宮問題。假設(shè)迷宮由m行n列構(gòu)成，有一個(gè)出口和一個(gè)入口，入口坐標(biāo)為（1,1），出口坐標(biāo)為（m,n），試設(shè)計(jì)并驗(yàn)證以下算法：找出一條從入口通往出口的路徑，或報(bào)告一個(gè)“無法通過〞的信息。

（1）用C語言實(shí)現(xiàn)順序存儲(chǔ)隊(duì)列上的基本操作，然后利用該隊(duì)列的基本操作找出迷宮的一條最短路徑。

（2）設(shè)計(jì)一個(gè)二維數(shù)組MAZE[m+2][n+2]表示迷宮，數(shù)組元素為0表示該位置可以通過，數(shù)組元素為1表示該位置不可以通行。MAZE[1][1]、MAZE[m][n]分別為迷宮的入口和出口。

（3）輸入迷宮的大小m行和n列，動(dòng)態(tài)生成二維數(shù)組；由隨機(jī)數(shù)產(chǎn)生0或1，建立迷宮，注意m*n的迷宮需要進(jìn)行擴(kuò)展，擴(kuò)展部分的元素設(shè)置為1，相當(dāng)于在迷宮周邊布上一圈不準(zhǔn)通過的墻。

（4）要求輸出模擬迷宮的二維數(shù)組；若存在最短路徑，則有出口回溯到入口（出隊(duì)列并利用棧實(shí)現(xiàn)），再打印從入口到出口的這條路徑，例如（1,1），，（i,j），，（m,n）；若沒有路徑，則打印“Nopath〞。

（5）迷宮的任一位置（i,j）上均有八個(gè)可移動(dòng)的方向，用二維數(shù)組Direction存放八個(gè)方向的位置偏移量。

Direction[8][2]={{0,1}，{1,1}，{0，-1}，{-1，-1}，{1,-1}，{1,0}，{-1,0}，{-1,1}}；（6）為避免出現(xiàn)原地踏步的狀況需要標(biāo)志已經(jīng)通過的位置，采用一個(gè)標(biāo)志數(shù)組MARK[m+2][n+2]，初值均為0，在尋覓路徑的過程中，若通過了位置（i，j），則將MARK[i][j]置為1。

（7）為了記錄查找過程中到達(dá)位置（i，j）及首次到達(dá)（i,j）的前一位置（i_pre,j_pre），需要記住前一位置（i_pre,j_pre）在隊(duì)列中的序號(hào)pre，即隊(duì)列中數(shù)據(jù)元素應(yīng)當(dāng)是一個(gè)三元組（i,j,pre）。

（8）探尋過程簡(jiǎn)單下：將入口MAZE[1][1]作為第一個(gè)出發(fā)點(diǎn)，依次在八個(gè)方向上探尋可通行的位置，將可通行位置（i,j,pre）入隊(duì)，形成第一層新的出發(fā)點(diǎn)，然后依次出隊(duì)，即對(duì)第一層中各個(gè)位置分別探尋它所在八個(gè)方向上的可通行位置，形成其次層新的出發(fā)點(diǎn)，...，如此進(jìn)行下去，直至達(dá)到出口MAZE[m][n]或者迷宮所有位置都探尋完畢為止。

二、試驗(yàn)過程及結(jié)果

一、需求分析

1、用棧的基本操作完成迷宮問題的求解，其中棧的基本操作作為一個(gè)獨(dú)立的模塊存在。2、以二維數(shù)組M[m+2][n+2]表示迷宮，M[i][j]表示迷宮中相應(yīng)（i,j）位置的通行狀態(tài)（0:表示可以通行，1：表示有墻，不可通行），完成迷宮的抽象數(shù)據(jù)類型，包括出口、入口位置等。

3、用戶從屏幕上輸入迷宮，從鍵盤輸入迷宮的大小，即迷宮的長(zhǎng)和寬(由于控制臺(tái)大小限制，輸入的長(zhǎng)寬需在50以下)，完成對(duì)應(yīng)迷宮的初始化。根據(jù)鍵盤輸入的迷宮規(guī)格隨機(jī)生成大小一致的迷宮，產(chǎn)生方塊的地方為墻，無方塊的地方可通過，如下例所示：如下所示：

4、程序完成對(duì)迷宮路徑的探尋，為了更好地顯示出求解結(jié)果，假使存在路徑，則以長(zhǎng)方形形式將迷宮打印出來，而不是只按步輸出坐標(biāo)，也便于檢查路徑的正確性，用特定符號(hào)標(biāo)出迷宮的物理狀態(tài)，其中字符“#〞表示出口和入口，“

M->Maze[0][k]=1;for(j=0;jMaze[j][0]=1;for(j=0;jMaze[j][width+1]=1;for(k=0;kMaze[length+1][k]=1;//設(shè)置迷宮圍墻for(j=1;jMaze[j][k]=rand()%2;//隨機(jī)生成迷宮}

M->length=length;M->width=width;M->start.row=1;M->start.col=1;M->end.row=M->length;M->end.col=M->width;M->Maze[M->start.row][M->start.col]=M->Maze[M->end.row][M->end.col]=0;//入口和出口設(shè)置*/}

voidPrintMaze(MAZEM){//打印出迷宮，包括邊界

printf(\迷宮入口:[1,1]--用#表示\\n\printf(\迷宮出口:[%d,%d]--用#表示\\n\for(row=0;rowbase)exit(OVERFLOW);S->top=S->base;//空棧的棧頂和棧底位置一致S->stacksize=STACK_INIT_SIZE;returnOK;

}

StatusStackEmpty(SqStack*S){if(S->top==S->base)returnTRUE;elsereturnFALSE;}

StatusPush(SqStack*S,SElemType*e)//在棧頂插入新的元素，入棧{if(S->top-S->base>=S->stacksize){S->base=(SElemType

*)realloc(S->base,(S->stacksize+STACKINCRENT)*sizeof(SElemType));//重新分派空間if(!S->base)exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCRENT;}*S->top++=*e;returnOK;}

StatusGetTop(SqStack*S,SElemType*e)//從棧中取元素{if(S->top==S->base)returnERROR;*e=*(S->top-1);re