數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)--騎士游歷

1、<p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2011 ～2012 學(xué)年第 二 學(xué)期</p><p>　　2012 年6 月10 日</p><p><b>　　題目：</b></p>

2、;<p><b>　　名稱：騎士游歷</b></p><p>　　內(nèi)容：給你一個(gè)8*8的棋盤(pán),騎士的開(kāi)始位置,結(jié)束位置,讓你求得騎士從開(kāi)始位置開(kāi)始走到結(jié)束位置需要最小的步數(shù)是多少？（注意,騎士走日字）</p><p><b>　　要求：</b></p><p>　　（1）輸入：輸入包含多組數(shù)據(jù)，每一行都是一組

3、開(kāi)始位置和結(jié)束位置,位置由兩個(gè)字符組成,一個(gè)是小寫(xiě)字母(a-h),一個(gè)是數(shù)字(1-8),起始位置結(jié)束位置由一個(gè)空格隔開(kāi).</p><p>　?。?）輸出：輸出從起始位置到結(jié)束位置,騎士所要走過(guò)的最小的步數(shù).</p><p>　　（3）所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)應(yīng)盡可能節(jié)省存儲(chǔ)空間。</p><p>　?。?）程序的運(yùn)行時(shí)間應(yīng)盡可能少。</p><p>

4、<b>　　問(wèn)題分析和任務(wù)定義</b></p><p>　　此程序需要完成如下要求：給你一個(gè)8*8的棋盤(pán),騎士的開(kāi)始位置,結(jié)束位置,讓你求得騎士從開(kāi)始位置開(kāi)始走到結(jié)束位置需要最小的步數(shù)是多少？（注意,騎士走日字）</p><p>　　實(shí)現(xiàn)本程序需要解決以下幾個(gè)問(wèn)題：</p><p>　　如何表示8*8的棋盤(pán)，確定棋盤(pán)上各點(diǎn)的位置。</p&

5、gt;<p>　　馬在棋盤(pán)上的各種行走方法怎樣來(lái)表示，行走過(guò)程如何實(shí)現(xiàn)。</p><p>　　如何表示位置由兩個(gè)字符組成,一個(gè)是小寫(xiě)字母(a-h),一個(gè)是數(shù)字(1-8)。</p><p>　　如何找到一條滿足條件的路徑。</p><p>　　如何確定這條路徑是最短的。</p><p>　　本問(wèn)題的關(guān)鍵和難點(diǎn)是如何根據(jù)騎士的走法規(guī)

6、則，找出一條最短路徑。</p><p><b>　　圖1:8*8的棋盤(pán)</b></p><p>　　如圖，建立如上的坐標(biāo)系，于是每個(gè)點(diǎn)的位置就可以用一個(gè)有序數(shù)對(duì)來(lái)表示。如：（a,3）,（b,6）,（h,2）。</p><p>　　對(duì)于任意一點(diǎn)的馬最多有8中走法可以選擇。根據(jù)馬行走后行列坐標(biāo)數(shù)值大小的增加和減少情況的變化，用有序數(shù)組對(duì)來(lái)表示其走法

7、。</p><p>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　其中，bx數(shù)組與by數(shù)組下標(biāo)相同的變量表示一種走法。</p><p>　　騎士在棋盤(pán)中的位置可由結(jié)構(gòu)體類型<

8、;/p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int n,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node; <

9、/b></p><p><b>　　來(lái)表示。</b></p><p>　　對(duì)于騎士的起始與終點(diǎn)位置可由有序?qū)?x0,y0),(x1,y1)來(lái)表示。</p><p><b>　　另外建立一個(gè)隊(duì)列，</b></p><p>　　typedef struct //定義順序隊(duì)

10、列類型</p><p><b>　　{</b></p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p>　　}Sequeue; </p>&l

11、t;p>　　把騎士從起點(diǎn)到終點(diǎn)的每一步入隊(duì)，前一步出對(duì)。</p><p>　　概要設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)選擇</p><p>　　對(duì)于所提出的關(guān)鍵問(wèn)題，即找出從起點(diǎn)到終點(diǎn)的最短步數(shù)，這里所用到的方法是遍歷起點(diǎn)與終點(diǎn)的所有路徑，記錄下其步數(shù)，然后比較其中最小的步數(shù)，即為最短步數(shù)。</p><p>　　輸入起點(diǎn)和終點(diǎn)的坐標(biāo)，起點(diǎn)先入對(duì)；</p><p&

12、gt;　　按照上述的8走法分別走一步，如果到達(dá)終點(diǎn)，計(jì)步器加一，如果未到終點(diǎn)，計(jì)步器加一并入對(duì)；（所有走法均入隊(duì)）</p><p>　　出對(duì)，以步驟2中的如對(duì)順序分別把其作為新起點(diǎn)，重復(fù)步驟2；</p><p>　　判斷是否對(duì)空，對(duì)空則以走過(guò)全部路徑，對(duì)未空，重復(fù)步驟3；對(duì)空，轉(zhuǎn)到步驟5；</p><p>　　比較每種路徑的步數(shù)，選出最小的數(shù)值，即為最小步數(shù)。<

13、;/p><p>　　以上操作相當(dāng)于對(duì)于一棵8個(gè)結(jié)點(diǎn)的完全樹(shù)進(jìn)行遍歷，查找滿足條件的結(jié)點(diǎn)，并找出這些結(jié)點(diǎn)中結(jié)點(diǎn)高度最低的結(jié)點(diǎn)。 </p><p>　　以上過(guò)程可由樹(shù)來(lái)表示。樹(shù)如圖2：</p><p><b>　　…… ……</b></p><p>　　…… …… …… ……

14、 ……</p><p>　　…… …… …… …… …… ……</p><p>　　圖2：騎士游歷的樹(shù)結(jié)構(gòu)</p><p>　　如圖3，先找到起點(diǎn)，即根節(jié)點(diǎn)，并進(jìn)行入隊(duì)操作。由起點(diǎn)逐次訪問(wèn)起點(diǎn)的各個(gè)子樹(shù)的根節(jié)點(diǎn)，比較是否等于終點(diǎn)的坐標(biāo)，若相等，則保存路徑長(zhǎng)度；若不相等，則把不相等

15、的子樹(shù)的根節(jié)點(diǎn)進(jìn)行入隊(duì)操作。訪問(wèn)完所有子樹(shù)的根節(jié)點(diǎn)后，進(jìn)行一次出隊(duì)操作；即把根節(jié)點(diǎn)出隊(duì)。此后順次訪問(wèn)隊(duì)頭節(jié)點(diǎn)的子樹(shù)的根節(jié)點(diǎn)，即順次訪問(wèn)根節(jié)點(diǎn)的子樹(shù)的根節(jié)點(diǎn)的各個(gè)子樹(shù)的根節(jié)點(diǎn)，比較是否等于終點(diǎn)的坐標(biāo)，若相等，則保存路徑長(zhǎng)度；若不相等，則把不相等的子樹(shù)的根節(jié)點(diǎn)進(jìn)行入隊(duì)操作。直到隊(duì)為空為止。</p><p><b>　　訪問(wèn)順序如下：</b></p><p>　　…

16、 …… …</p><p><b>　　…</b></p><p>　　圖3：游歷的訪問(wèn)順序</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)如下：</b></p><p>　　typedef struct //騎士位置結(jié)構(gòu)體</p><p>&

17、lt;b>　　{</b></p><p>　　int n,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node;</b></p><p>　　typedef struct //

18、順序隊(duì)列類型結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p><b>　　}Sequeue;&l

19、t;/b></p><p>　　圖4：詳細(xì)設(shè)計(jì)流程圖</p><p><b>　　詳細(xì)設(shè)計(jì)和編碼</b></p><p>　　首先，對(duì)于在問(wèn)題分析和任務(wù)定義中所提出的問(wèn)題逐個(gè)進(jìn)行解決。</p><p>　　定義棋盤(pán)和走法，并對(duì)其進(jìn)行初始化。</p><p>　　int way[8][8] 表

20、示棋盤(pán)每一點(diǎn)的位置，例如，way[2][2]表示第三行，第三列的坐標(biāo)，way[3][6]表示第四行，第七列的坐標(biāo)。因?yàn)樵诒緦?shí)驗(yàn)中并沒(méi)有要求騎士行走的路徑，所以棋盤(pán)可不顯示的定義。</p><p>　　對(duì)于走法，我們前面已經(jīng)提到了，對(duì)于馬在棋盤(pán)中的任意位置，最多有8種走法，用有序數(shù)對(duì)表示即：(2,1),(2,-1)(1,2),(1.-2)(-2,1),(-2,-1),(-1,2),(-1,-2)。故，我們可以做如下

21、定義：</p><p>　　根據(jù)馬行走后行列坐標(biāo)數(shù)值大小的增加和減少情況的變化，用有序數(shù)組對(duì)來(lái)表示其走法。</p><p>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　其中，b

22、x數(shù)組與by數(shù)組下標(biāo)相同的變量表示一種走法。所以在騎士的行走過(guò)程中，只要讓騎士的位置即坐標(biāo)加上或減去上述8中走法的數(shù)組表示。</p><p>　　對(duì)于騎士的起點(diǎn)和終點(diǎn)的位置表示，根據(jù)要求位置由兩個(gè)字符組成,一個(gè)是小寫(xiě)字母(a-h),一個(gè)是數(shù)字(1-8)。所以有如下的表示方法：</p><p>　　int x0,y0,x1,y1; char xa，xb；x0=xa-‘a(chǎn)’; x1=xb-

23、‘a(chǎn)’;</p><p>　　其中，x0、y0表示起點(diǎn)坐標(biāo)，x1、y1表示終點(diǎn)坐標(biāo)，輸入的xa，xb為字符，減去‘a(chǎn)’，便可轉(zhuǎn)換成數(shù)字。這樣便可以把輸入的字符坐標(biāo)轉(zhuǎn)換成用數(shù)字表示的坐標(biāo)。</p><p>　　在得到騎士的起點(diǎn)終點(diǎn)坐標(biāo)之后，便可以把起點(diǎn)入隊(duì)，入隊(duì)函數(shù)如下所示：</p><p>　　void add(Sequeue *S,int x,int y,int

24、z) //入隊(duì)函數(shù)</p><p><b>　　{</b></p><p>　　if(S->rear<maxlen-1 && S->rear>=0)</p><p><b>　　{</b></p><p>　　S->rear++;</p&g

25、t;<p>　　S->data[S->rear].n=x;</p><p>　　S->data[S->rear].m=y;</p><p>　　S->data[S->rear].ch=z;</p><p><b>　　}</b></p><p>　　else pri

26、ntf("error\n");</p><p><b>　　}</b></p><p>　　這里的參數(shù)x，y，z分別表示行坐標(biāo)，列坐標(biāo)，和到達(dá)該坐標(biāo)從起點(diǎn)所走的步數(shù)。它們的值分別保存在隊(duì)列的n，m，ch中。</p><p>　　在對(duì)起點(diǎn)進(jìn)行入隊(duì)之后，便可進(jìn)行運(yùn)動(dòng)了，即騎士可以按規(guī)則(8種走法)走向下一位置。</p>

27、;<p>　　此后，在一個(gè)while循環(huán)中進(jìn)行如下的操作，while循環(huán)的條件為：S->front<S->rear，保證在隊(duì)列不為空的情況下進(jìn)行循環(huán)。</p><p>　　對(duì)于騎士的8種走法，可以通過(guò)for(i=0;i<8;i++)循環(huán)進(jìn)行逐個(gè)試探。這里可以定義兩個(gè)證型變量x3、y3；用以存放騎士走一步后的位置，即坐標(biāo)。則有如下定義：</p><p>

28、　　x3=bx[i]+x0; y3=by[i]+y0;</p><p>　　又由實(shí)際情況可知，x3、y3應(yīng)該滿足x3、y3同時(shí)大于等于0且小于8；在此時(shí)設(shè)置標(biāo)記數(shù)組step[maxlen][maxlen]=0;標(biāo)記數(shù)組用以標(biāo)記該位置是否已經(jīng)走過(guò)，走過(guò)則置1；所以x3、y3還應(yīng)滿足step[x3][y3]==0;即(x3,y3)這個(gè)位置還未走過(guò)。若滿足以上條件，則可以定義node *p；并為其申請(qǐng)內(nèi)存空間。有如下一

29、段程序：</p><p>　　p=(node *)malloc(sizeof(node));</p><p>　　p->ch=S->data[S->front+1].ch+1;</p><p><b>　　p->n=x3;</b></p><p><b>　　p->m=y3;<

30、;/b></p><p>　　step[x3][y3]=1;</p><p>　　把(x3,y3)的值放入指針p指向的空間的（n，m）中，用以保存此位置；因?yàn)閏h存放的是從起點(diǎn)到該位置所走的步數(shù)，故p->ch=S->data[S->front+1].ch+1;即它表示的意思是從起點(diǎn)x3、y3所走的步數(shù)。此時(shí)并把x3y3的標(biāo)記置為1，說(shuō)明此位置已經(jīng)被訪問(wèn)過(guò)了。這時(shí)便可

31、以對(duì)x3、y3進(jìn)行判斷了。</p><p>　　若p->n==x1 && p->m==y1，即比較x3、y3與終點(diǎn)的坐標(biāo)是否相同。若相同則找到一種走法。此時(shí)定義 int a=0；int count[maxlen]; count[a]數(shù)組的作用就是記錄下每一種走法的步數(shù)；令count[a]=p->ch即可。若不滿足條件的話則把x3、y3入隊(duì)；</p><p&

32、gt;　　然后i++；重復(fù)上述操作，直到i不滿足條件為止，即已經(jīng)走完了8種走法；</p><p>　　此后，進(jìn)行出棧操作；判斷S->front與S->rear的大小關(guān)系，若S->front>S->rear,則進(jìn)行while循環(huán)，若不滿足，則跳出while循環(huán)。</p><p>　　最后，對(duì)計(jì)數(shù)數(shù)組count[a]中的值進(jìn)行比較，找出最小值，即為，從終點(diǎn)到起點(diǎn)的

33、最小步數(shù)。程序如下：</p><p><b>　　int min;</b></p><p>　　min=count[0];</p><p>　　for(i=1;i<a;i++)</p><p><b>　　{</b></p><p>　　if(min>count[

34、i])</p><p>　　min=count[i];</p><p><b>　　}</b></p><p>　　printf("最短步數(shù)為: %d\n",min);</p><p><b>　　上機(jī)調(diào)試</b></p><p>　　1、語(yǔ)法錯(cuò)誤及修正

35、：</p><p>　　本程序使用了循環(huán)思想和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，所以程序出現(xiàn)的語(yǔ)法錯(cuò)誤主要在于隊(duì)列函數(shù)的調(diào)用及變量的定義，關(guān)鍵字和函數(shù)名稱的書(shū)寫(xiě)，以及一些庫(kù)函數(shù)的規(guī)范使用。這些問(wèn)題均可以根據(jù)編譯器的警告提示，對(duì)應(yīng)的將其解決。</p><p>　　邏輯問(wèn)題的修改和調(diào)整：</p><p>　　循環(huán)思想的使用雖然簡(jiǎn)化了程序，但是增加了對(duì)函數(shù)循環(huán)控制的難度。在while循環(huán)中

36、，要實(shí)現(xiàn)對(duì)所有路徑的查找，而不能丟掉一條，也許丟掉的便是我們所需要的，這樣便造成了錯(cuò)誤。又因?yàn)槲覀儗?duì)路徑的查找使用了隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，即對(duì)坐標(biāo)進(jìn)行了入隊(duì)和出對(duì)的操作。所以我們可以用對(duì)空的條件作為while循環(huán)的終止條件。這樣便可以無(wú)遺漏的查找起點(diǎn)到終點(diǎn)的所有路徑。</p><p>　　還有一點(diǎn)容易出現(xiàn)邏輯錯(cuò)誤的是在何時(shí)進(jìn)行入隊(duì)和出對(duì)的操作。對(duì)入隊(duì)的操作而言，在每一次行走后對(duì)于不滿足條件的坐標(biāo)均要進(jìn)行入隊(duì)操作。而對(duì)于

37、出對(duì)而言，每次出隊(duì)操作均在對(duì)每一步的八種走法走完之后才進(jìn)行，這樣便可以保證路徑查找沒(méi)有遺漏。</p><p>　　時(shí)間，空間性能分析: </p><p>　　因?yàn)楸舅惴ㄐ枰靡粋€(gè)二維數(shù)組保存每一個(gè)位置的訪問(wèn)狀態(tài)，也需要一個(gè)一維數(shù)組保存訪問(wèn)到的滿足條件的步數(shù)，故其空間復(fù)雜度較高，會(huì)占據(jù)較大的內(nèi)存空間，其空間復(fù)雜度為O(maxlen*maxlen)。但是對(duì)于本算法而言，空間復(fù)雜度不但很高，時(shí)間

38、復(fù)雜度也很大。由于本算法將對(duì)路徑的遍歷轉(zhuǎn)變成了對(duì)樹(shù)的遍歷，需要遍歷所有的路徑并保存，從中找出滿足條件的路徑。所以無(wú)論起點(diǎn)和終點(diǎn)的位置如何，都需要進(jìn)行所有的查找過(guò)程，所以對(duì)于本算法而言，時(shí)間復(fù)雜度很大，為O(8^n*n)。由此可得，本算法的時(shí)間空間性能較差，由于知識(shí)的局限性，故本人無(wú)法對(duì)此算法進(jìn)行優(yōu)化。</p><p><b>　　4、經(jīng)驗(yàn)和體會(huì)：</b></p><p&g

39、t;　　在剛拿到此問(wèn)題時(shí)，感覺(jué)無(wú)從下手，但是經(jīng)過(guò)仔細(xì)的分析，了解到，對(duì)騎士路徑的查找，對(duì)八子樹(shù)的樹(shù)的遍歷算法很相像，不過(guò)要對(duì)每次遍歷的結(jié)果進(jìn)行判斷，從而找出滿足條件的結(jié)果。因此在具體解決問(wèn)題時(shí)采用了樹(shù)的數(shù)據(jù)結(jié)構(gòu)思想，再經(jīng)過(guò)完善和修改得出算法，并用程序語(yǔ)言實(shí)現(xiàn)。從這個(gè)過(guò)程中我了解到對(duì)問(wèn)題從認(rèn)識(shí)到建立模型，之后提出方法，修改方法，最終解決問(wèn)題的過(guò)程。也使我體會(huì)到對(duì)于具體問(wèn)題的解決，只要按照解決問(wèn)題的過(guò)程，就不會(huì)出現(xiàn)盲目的情況。</p&

40、gt;<p><b>　　用戶使用說(shuō)明</b></p><p>　　本程序運(yùn)行時(shí)帶有提示性語(yǔ)句。開(kāi)始時(shí)，程序會(huì)提示你輸入騎士游歷的起終點(diǎn)，輸入格式為每一行都是一組開(kāi)始位置和結(jié)束位置,位置由兩個(gè)字符組成,一個(gè)是小寫(xiě)字母(a-h),一個(gè)是數(shù)字(0-7),起始位置結(jié)束位置由一個(gè)空格隔開(kāi)。故輸入的坐標(biāo)橫坐標(biāo)的取值范圍在（a-h）之間，縱坐標(biāo)的取值范圍在（0-7）之間，輸入起終點(diǎn)位置后，

41、按回車，程序會(huì)給出從起點(diǎn)到終點(diǎn)的最短步數(shù)的值。之后，程序會(huì)提示你是否繼續(xù)輸入，輸入’y’表示繼續(xù)輸入，輸入‘n’表示不再進(jìn)行輸入，即退出程序。這樣便可以手動(dòng)的控制輸入的次數(shù)。方便查詢。</p><p><b>　　測(cè)試結(jié)果</b></p><p><b>　　圖五：運(yùn)行結(jié)果</b></p><p><b>　　附

42、錄</b></p><p>　　#include"stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#define maxlen 100</p><p>　　int length=0; //記錄所走的步數(shù)</p><p

43、>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int n

44、,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node;</b></p><p>　　typedef struct //定義順序隊(duì)列類型</p><p><b>　　{</b&g

45、t;</p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p><b>　　}Sequeue;</b></p><p>　　Sequeue *setqueue()

46、</p><p><b>　　{</b></p><p>　　Sequeue *S;</p><p>　　S=(Sequeue *)malloc(sizeof(Sequeue));</p><p>　　S->front=0;</p><p>　　S->rear=0;</p>

47、<p><b>　　return S;</b></p><p><b>　　}</b></p><p>　　void add(Sequeue *S,int x,int y,int z) //入隊(duì)函數(shù)</p><p><b>　　{</b></p><p>

48、　　if(S->rear<maxlen-1 && S->rear>=0)</p><p><b>　　{</b></p><p>　　S->rear++;</p><p>　　S->data[S->rear].n=x;</p><p>　　S->data[S

49、->rear].m=y;</p><p>　　S->data[S->rear].ch=z;</p><p><b>　　}</b></p><p>　　else printf("error\n");</p><p><b>　　}</b></p>

50、;<p>　　void dele(Sequeue *s) //出隊(duì)函數(shù)</p><p><b>　　{</b></p><p>　　if(s->front<s->rear)</p><p>　　s->front++;</p><p><b>　　else</b

51、></p><p>　　printf("error\n");</p><p><b>　　}</b></p><p>　　void judge() //判斷步數(shù) </p><p><b>　　{</b></p><p>　　Seque

52、ue *S;</p><p>　　S=setqueue();</p><p>　　int x0,y0,x1,y1,x3,y3,i,j; int count[maxlen+100];int a=0; int step[maxlen][maxlen];</p><p>　　char xa,xb;</p><p>　　for( i=0;i<

53、maxlen;i++)</p><p><b>　　{</b></p><p>　　S->data[i].ch=0;</p><p><b>　　}</b></p><p>　　printf("請(qǐng)輸入騎士游歷的起終點(diǎn)：\n");</p><p>　　

54、scanf(" %c,%d %c,%d",&xa,&y0,&xb,&y1);</p><p>　　x0=xa-'a';</p><p>　　x1=xb-'a';</p><p>　　for( i=0;i<maxlen;i++)</p><p>　　for

55、( j=0;j<maxlen;j++)</p><p><b>　　{</b></p><p>　　step[i][j]=0;</p><p><b>　　}</b></p><p>　　step[x0][y0]=1;</p><p>　　add(S,x0,y0,0);

56、</p><p>　　while(S->front<S->rear)</p><p><b>　　{</b></p><p><b>　　node *p;</b></p><p>　　x0=S->data[S->front+1].n;</p><p&

57、gt;　　y0=S->data[S->front+1].m;</p><p>　　for(int i=0;i<8;i++)</p><p><b>　　{</b></p><p>　　x3=bx[i]+x0;</p><p>　　y3=by[i]+y0;</p><p>　　if

58、(x3>=0 && x3<8 && y3>=0 && y3<8 && step[x3][y3]==0)</p><p><b>　　{</b></p><p>　　p=(node *)malloc(sizeof(node));</p><p>　　p->

59、;ch=S->data[S->front+1].ch+1;</p><p><b>　　p->n=x3;</b></p><p><b>　　p->m=y3;</b></p><p>　　step[x3][y3]=1;</p><p>　　if(p->n==x1 &am

60、p;& p->m==y1)</p><p><b>　　{</b></p><p>　　step[x1][y1]=0;</p><p>　　count[a]=p->ch;</p><p><b>　　a++;</b></p><p><b>　　

61、}</b></p><p><b>　　else</b></p><p>　　add(S,p->n,p->m,p->ch);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>&

62、lt;b>　　dele(S);</b></p><p><b>　　}</b></p><p><b>　　int min;</b></p><p>　　min=count[0];</p><p>　　for(i=1;i<a;i++)</p><p>

63、　　if(min>count[i])</p><p>　　min=count[i];</p><p>　　printf("最短步數(shù)為: %d\n",min);</p><p><b>　　}</b></p><p>　　void main()</p><p><b

64、>　　{</b></p><p><b>　　char nn;</b></p><p><b>　　nn='y';</b></p><p>　　while(nn=='y')</p><p><b>　　{</b></p&g

65、t;<p><b>　　judge();</b></p><p>　　printf("是否繼續(xù)輸入？('y'是,'n'否)\n");</p><p>　　scanf(" %c",&nn);</p><p><b>　　}</b>&