廣度優(yōu)先搜索

1、廣度優(yōu)先搜索廣度優(yōu)先搜索在樹中又叫按層次遍歷，對于樹而言，寬度廣度優(yōu)先搜索在樹中又叫按層次遍歷，對于樹而言，寬度優(yōu)先搜索的思路可以描述為：訪問根結(jié)點，依次訪問根結(jié)優(yōu)先搜索的思路可以描述為：訪問根結(jié)點，依次訪問根結(jié)點的每一個子結(jié)點（第二層），再通過這些結(jié)點訪問第三點的每一個子結(jié)點（第二層），再通過這些結(jié)點訪問第三層結(jié)點層結(jié)點。廣度優(yōu)先與深度優(yōu)先搜索相比，時間復雜度。廣度優(yōu)先與深度優(yōu)先搜索相比，時間復雜度都是相同的，不同的僅僅在于結(jié)點訪問的順序不同。它們都是相同的，不同的僅僅在于結(jié)點訪問的順序不同。它們在完全遍歷的問題上應該是差不多，但是在有些問題上，在完全遍歷的問題上應該是差不多，但是在有些問題

2、上，比如求最優(yōu)解，有時廣度優(yōu)先要比深度優(yōu)先搜索好。比如求最優(yōu)解，有時廣度優(yōu)先要比深度優(yōu)先搜索好。為了求一個最優(yōu)解，如果使用深度優(yōu)先并不能保證找到的為了求一個最優(yōu)解，如果使用深度優(yōu)先并不能保證找到的解最優(yōu)，只有搜索完整棵樹，找到所有解，再比較它們的解最優(yōu)，只有搜索完整棵樹，找到所有解，再比較它們的優(yōu)劣，才能從中求出最優(yōu)解，這顯然不如廣度優(yōu)先搜索簡優(yōu)劣，才能從中求出最優(yōu)解，這顯然不如廣度優(yōu)先搜索簡單。單。一般來說廣度優(yōu)先搜索可以利用隊列實現(xiàn)，主要用于解決一般來說廣度優(yōu)先搜索可以利用隊列實現(xiàn)，主要用于解決求一種狀態(tài)通過幾種規(guī)定的操作以最少次數(shù)變換到另一種求一種狀態(tài)通過幾種規(guī)定的操作以最少次數(shù)變換到另

3、一種狀態(tài)的問題。狀態(tài)的問題。引例經(jīng)過城市最少的一條路徑狀態(tài)描述（矩陣表示）：1表示不相鄰 0表示相鄰const ju:array1.8,1.8of 0.1=(1,0,0,0,1,0,1,1), (0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1);結(jié)點定義type node=record city:char;城市名稱 pre:integer;父結(jié)點end;varhead,tail,i:i

4、nteger;隊列首與隊列尾a:array1.100of node;結(jié)點數(shù)s:arrayA.Hof boolean;城市數(shù)procedure out(d:integer);輸出過程，通過每個結(jié)點的父結(jié)點來輸出Begin write(ad.city); repeat d:=ad.pre; write(-,ad.city); until ad.pre=0; writeln;end;procedure doit;begin head:=0;tail:=1;入隊 a1.city:=A;a1.pre:=0;初始化從A結(jié)點開始擴展 fillchar(s,sizeof(s),true);所有結(jié)點可用 rep

5、eat inc(head);隊首加，出隊 for i:=1 to 8 do訪問可擴展的結(jié)點 if (juord(ahead.city)-64,i=0)and (schr(i+64)=true)then結(jié)點可用 begin inc(tail);入隊 atail.city:=chr(64+i); atail.pre:=head;記住它的父結(jié)點以便輸出 satail.city:=false;該結(jié)點標志為已用 if atail.city=H then判斷是否到達目標結(jié)點 begin out(tail);輸出 break;退出搜索，因為已找到最優(yōu)解 end; end; until head=tail;e

6、nd;begin doit;end.主程序主程序小結(jié)廣度優(yōu)先搜索相當于鐘擺！圖2 搜索樹擴展根節(jié)點葉子節(jié)點4,5,6,7,81112131415161718小結(jié)廣度優(yōu)先算法描述：Program bfs; 初始化，初始狀態(tài)存入隊列；隊列首指針head:=0;尾指針tail:=1;While headtail do begin 指針head后移一位，指向待擴展的結(jié)點；for i:=1 to maxdo begin if 擴展出的新結(jié)點是目標結(jié)點 then 輸出并退出；if 擴展出的新結(jié)點符合條件，并且新結(jié)點與原已產(chǎn)生的結(jié)點不重復 then tail指針加，把新結(jié)點存入隊列尾；end;End;注意事

7、項注意事項、每生成一個子結(jié)點，就要提供指向它們父結(jié)點的指針。當、每生成一個子結(jié)點，就要提供指向它們父結(jié)點的指針。當解出現(xiàn)時，通過逆向跟蹤，找到從根結(jié)點到目標結(jié)點的一條路解出現(xiàn)時，通過逆向跟蹤，找到從根結(jié)點到目標結(jié)點的一條路徑。徑。、生成的結(jié)點要與前面所有已經(jīng)產(chǎn)生的結(jié)點比較，以免出現(xiàn)、生成的結(jié)點要與前面所有已經(jīng)產(chǎn)生的結(jié)點比較，以免出現(xiàn)重復結(jié)點，浪費時間和空間，還有可能陷入死循環(huán)。重復結(jié)點，浪費時間和空間，還有可能陷入死循環(huán)。、如果目標結(jié)點的深度與、如果目標結(jié)點的深度與“費用費用”（如路徑長度）成正比，（如路徑長度）成正比，那么找到的第一個解即為最優(yōu)解，這時，搜索速度比深度搜索那么找到的第一個解即

8、為最優(yōu)解，這時，搜索速度比深度搜索要快些。如果結(jié)點的要快些。如果結(jié)點的“費用費用”不與深度成正比時，第一次找到不與深度成正比時，第一次找到的解不一定是最優(yōu)解。的解不一定是最優(yōu)解。、廣度優(yōu)先搜索的效率還有賴于目標結(jié)點所在位置情況，如、廣度優(yōu)先搜索的效率還有賴于目標結(jié)點所在位置情況，如果目標結(jié)點深度處于較深層時，需搜索的結(jié)點數(shù)基本上以指數(shù)果目標結(jié)點深度處于較深層時，需搜索的結(jié)點數(shù)基本上以指數(shù)增長，這時一般要采用循環(huán)隊列來儲存擴展結(jié)點。增長，這時一般要采用循環(huán)隊列來儲存擴展結(jié)點。 設有下圖所示的一個棋盤，在棋盤上的設有下圖所示的一個棋盤，在棋盤上的A(0,0)點有一個中國象棋馬，點有一個中國象棋馬，

9、并約定馬走的規(guī)則：并約定馬走的規(guī)則： 1、馬只向右走；、馬只向右走； 2、馬走、馬走“日日“字。字。找出所有從找出所有從A到到B的路徑。的路徑。輸入：輸入：B的坐標的坐標n，m（=15）。）。輸出：所有走法。輸出：所有走法。如：如：輸入：輸入：8 4輸出：（輸出：（0,0)(2 1)(4 0)(5 2)(6 0)(7 2)(8 4)共共37組解見組解見tmall.txt1234567123跳馬問題最小步數(shù)跳馬問題最小步數(shù)最優(yōu)解輸出結(jié)果為：最優(yōu)解輸出結(jié)果為：（8，4）（6，3）（4，2）（2，1），），-（0，0）求最少步到達求最少步到達B點。點。Best:最短路線，最短路線，a：臨時得到的一個

10、路線。：臨時得到的一個路線。Min：最少步。：最少步。procedure try(i:integer); 搜索到當前第搜索到當前第i個點個點 var j:integer; begin if (ai,1=n) and (ai,2=m)and(imin) then begin min:=i;best:=a;exit;end; 記下當前最短路徑和最少步數(shù)記下當前最短路徑和最少步數(shù) if (ai,1n) or (ai,2m)and(i=min) then exit; 剪枝優(yōu)化剪枝優(yōu)化 for j:=1 to 4 do if (ai,1+xj,1=0)and(ai,1+xj,1=0)and(ai,2+x

11、j,2=m) then begin ai+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2; try(i+1); end; end;我們可以參照工作分配中求最大效益的方法來求解我們可以參照工作分配中求最大效益的方法來求解缺點：缺點：很明顯，要找到一條跳的步數(shù)最小的路徑，必須把很明顯，要找到一條跳的步數(shù)最小的路徑，必須把所有路徑全部跳完后才能判斷哪一條是最優(yōu)路徑，所有路徑全部跳完后才能判斷哪一條是最優(yōu)路徑，搜索效率比較低。搜索效率比較低。廣度搜索求解跳馬問題狀態(tài)產(chǎn)生規(guī)則狀態(tài)產(chǎn)生規(guī)則const dx:array1.4 of integer=(1,2,2,1); dy:array1

12、.4 of integer=(2,1,-1,-2);type node=record lx,ly:integer; pre:integer;父結(jié)點，輸出時用 end;var a:array0.1000of node; h,t,n,m,i,x,y:integer;procedure print;輸出，倒著輸出直到父結(jié)點變成始結(jié)點止begin while at.pre0 do begin write(at.lx,at.ly,-); t:=at.pre; end; writeln(0,0); halt;由于搜索到的肯定是最優(yōu)解所以程序運行結(jié)束end;begin readln(n,m); h:=0;

13、t:=1; a1.lx:=0;記錄始狀態(tài) a1.ly:=0; a1.pre:=0; while h=1)and(x=1)and(y=m) then begin inc(t);入隊 at.pre:=h;記住父結(jié)點 at.lx:=x; at.ly:=y;記錄新結(jié)點 if (x=n) and (y=m) then print;是否到達 end; end; end;writeln(No solution)end.輸出結(jié)果為：8，46，34，22，1-0，0【基礎】走迷宮 題目描述題目描述迷宮由N*N個方格組成，每個方格均被組織者事先標上了“0”或“1”（左上角第一個方格和右下角最后一個方格一定是“0”

14、）。當你進入左上角的第一個方格中時，看到相鄰的方格是“0”時則可以進入，而如果是“1”時則表示此路不通。兔兔被告之：從迷宮的左上角第一個方格的入口處準備進入時，你可得到一個記有N*N分值的記分表，每經(jīng)過一個標有“0”的方格，記分表將自動扣去1分，當走到右下角最后一個方格的出口處時，將顯示你手中的記分表剩余的分值。夏令營的組織者將只獎勵所有參加此項活動中，記分表剩余的分值最多的營員。輸入輸入第一行是一個整數(shù)N（3N40），接下來有N行，每行均有N個由0 和1組成的數(shù)據(jù)輸出輸出包括一個整數(shù)（記分表剩余的分值）樣例輸入樣例輸入4 00111000 00011000 樣例輸出樣例輸出9解題思想：此題本

15、質(zhì)上還是求最短的路徑，因為求剩余的價值最大，也就是意味著要走過的路最短這樣減少的值就會少！另外，對于此題不要求輸出最短的路徑，所以變量定義時可以考慮更少，不用再記錄所走過的每個結(jié)點的位置，而且根據(jù)廣度優(yōu)先搜索的原理，從一個結(jié)點擴展到下一層結(jié)點，所剩余的值就是父結(jié)點的值減一即可，到了最后的目標結(jié)點，剩余的值就是所求的值。注意事項：輸入是字符，不是數(shù)字0，1來源來源武進區(qū)第4屆程序設計比賽題（初中）const dx:array1.4of integer=(1,0,-1,0);坐標增量 dy:array1.4of integer=(0,1,0,-1);type node=record s,x,y:i

16、nteger;S表示剩余的值，初值為n*n，x,y表示位置 end;varq:array1.100000of node;隊列a:array1.100,1.100of char;狀態(tài)變量h,t,i,j,n,lx,ly:longint;狀態(tài)產(chǎn)生規(guī)則begin readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j);由于讀入是字符，務必請注意 readln; end; h:=0;t:=1;q1.s:=n*n-1;q1.x:=1;q1.y:=1;a1,1:=1;從第一個結(jié)點開始，初值為n*n-1 repeat inc(h);出隊 fo

17、r i:=1 to 4 do遍歷所有結(jié)點 begin lx:=qh.x+dxi;ly:=qh.y+dyi; if (lx in 1.n)and(ly in 1.n)and(alx,ly=0) then結(jié)點可用 begin inc(t);入隊 qt.s:=qh.s-1;該結(jié)點的剩余值為父結(jié)點的值減一 qt.x:=lx;記錄位置，便于下次擴展用 qt.y:=ly; if (lx=n)and(ly=n) then begin writeln(qt.s);halt;end;如果到了目標結(jié)點直接輸出 alx,ly:=1;該結(jié)點標志為已用過，以免重復入隊 end; end; until h=t;end.例

18、例3-13-1：（：（xibaoshumuxibaoshumu.txt.txt） 一矩形陣列由數(shù)字一矩形陣列由數(shù)字0 0到到9 9組成組成, ,數(shù)字數(shù)字1 1到到9 9代表細胞代表細胞, ,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞一細胞, ,求給定矩形陣列的細胞個數(shù)。求給定矩形陣列的細胞個數(shù)。輸入：整數(shù)輸入：整數(shù)m,n(mm,n(m行，行，n n列列) ) 矩陣矩陣輸出：細胞的個數(shù)。輸出：細胞的個數(shù)。樣例樣例: :輸入輸入: : 4 10 4 100234500067023450006710345605001034560500204

19、5600671204560067100000000890000000089輸出輸出:4:40234500067103456050020456006710000000089共共4 4個細胞個細胞算法步驟：算法步驟： 1 1、從文件中讀入、從文件中讀入m m* *n n矩陣，將其轉(zhuǎn)換為矩陣，將其轉(zhuǎn)換為0 0、1 1矩陣存入矩陣存入picpic數(shù)組中；數(shù)組中； 2 2、沿、沿picpic數(shù)組矩陣從上到下，從左到右，找到遇到的第數(shù)組矩陣從上到下，從左到右，找到遇到的第一個細胞；將細胞的位置入隊一個細胞；將細胞的位置入隊h h，并沿其上、下、左、右，并沿其上、下、左、右四個方向上搜索，如果遇到細胞四個方

20、向上搜索，如果遇到細胞(picI,j(picI,j=1)=1)則將其位置入隊，則將其位置入隊，入隊后的位置入隊后的位置picI,jpicI,j 數(shù)組置為數(shù)組置為0 0； 3 3、將、將h h隊的隊頭出隊，沿其上、下、左、右四個方向上隊的隊頭出隊，沿其上、下、左、右四個方向上搜索，如果遇到細胞則將其位置入隊，入隊后的位置搜索，如果遇到細胞則將其位置入隊，入隊后的位置picpic數(shù)數(shù)組置為組置為0 0； 4 4、重復、重復3 3，直至，直至h h隊空為止，則此時找出了一個細胞；隊空為止，則此時找出了一個細胞； 5 5、重復、重復2 2，直至矩陣找不到細胞；，直至矩陣找不到細胞； 6 6、輸出找到的

21、細胞數(shù)。、輸出找到的細胞數(shù)。const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1);var s:string; pic:array1.50,1.80 of 0.1; 0:無細胞；無細胞；1：有細胞：有細胞 m,n,i,j,num:integer; h:array1.4000,1.2 of byte; 隊列：存細胞的坐標，隊列：存細胞的坐標，1：行；：行；2：列：列procedure doing(i,j:integer); var k,open,closed,x,y:integer; begin inc(num);

22、 pici,j:=0; open:=0; 隊列頭隊列頭 closed:=1; 隊列尾隊列尾 h1,1:=i; h1,2:=j;遇到的第一個細胞入隊遇到的第一個細胞入隊 while open0) and (x0) and (y=n) and (picx,y=1) (x,y)處有細胞處有細胞 then begin inc(closed);進隊列進隊列 hclosed,1:=x;hclosed,2:=y; picx,y:=0;打刪除標志打刪除標志 end;為細胞的入隊為細胞的入隊 end; end;begin fillchar(pic,sizeof(pic),0); num:=0; fillchar

23、(h,sizeof(h),0); assign(input,a.in);reset(input); assign(output,a.out);rewrite(output); readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩陣中尋找細胞 writeln(num); close(input); close

24、(output);end.八數(shù)碼問題在在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有18中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結(jié)構(gòu)，給出一個初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀結(jié)構(gòu)，給出一個初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀態(tài)），問如何移動將牌，才能實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)換。態(tài)），問如何移動將牌，才能實現(xiàn)從

25、初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)換。圖圖1八數(shù)碼問題的初始和目標狀態(tài)八數(shù)碼問題的初始和目標狀態(tài)狀態(tài)表示：顯然用二維數(shù)組來表示布局直觀，狀態(tài)表示：顯然用二維數(shù)組來表示布局直觀，S（I,j）表示第）表示第I行第行第J列列格子上放的數(shù)字?？崭裼酶褡由戏诺臄?shù)字?？崭裼?表示；表示；移動規(guī)則：根據(jù)題意空格周圍的棋子可以向空格移動。為便于解決問移動規(guī)則：根據(jù)題意空格周圍的棋子可以向空格移動。為便于解決問題，顯然從另一個角度來看，空格周圍的棋子可以向空格移動相當于題，顯然從另一個角度來看，空格周圍的棋子可以向空格移動相當于“空格向四周移動空格向四周移動”，這樣就把四枚棋子的移動轉(zhuǎn)化為一個空格的移，這樣就把四枚棋子的移

26、動轉(zhuǎn)化為一個空格的移動，從而便于問題的處理。動，從而便于問題的處理。移動規(guī)則：移動規(guī)則：1、向上移動、向上移動Y+12、向下移動、向下移動Y-13、向左移動、向左移動X-14、向右移動、向右移動X+1搜索策略：搜索策略：1、把初始狀態(tài)作為當前狀態(tài)；、把初始狀態(tài)作為當前狀態(tài)；2、從當前的狀態(tài)出發(fā)，運用四條移動規(guī)則，產(chǎn)生新的、從當前的狀態(tài)出發(fā)，運用四條移動規(guī)則，產(chǎn)生新的狀態(tài)狀態(tài)3、判斷新的狀態(tài)是否達到目標狀態(tài)，如果是，轉(zhuǎn)、判斷新的狀態(tài)是否達到目標狀態(tài)，如果是，轉(zhuǎn)5；4、把新的狀態(tài)記錄下，取出下一個中間狀態(tài)作為當前、把新的狀態(tài)記錄下，取出下一個中間狀態(tài)作為當前狀態(tài)，返回狀態(tài)，返回2；5、輸出從初始狀

27、態(tài)到目標狀態(tài)的路徑，結(jié)束。、輸出從初始狀態(tài)到目標狀態(tài)的路徑，結(jié)束。const n:array1.4,1.2of integer=(1,0),(-1,0),(0,1),(0,-1);四個規(guī)則type arr=array1.3,1.3of integer;var a,b:Arr; list:array1.10000of arr;隊列，存放結(jié)點 fa:array1.10000of integer;記錄父結(jié)點 t:integer; i,o,j,x,y:integer; found:boolean;判斷是否到達目標結(jié)點function f(c,d:arr):boolean;var k,l:integer

28、;begin f:=true; for k:=1 to 3 do for l:=1 to 3 do if ck,ldk,l then f:=false;end;判斷是否已經(jīng)存放在隊列中function pa(c:arr):boolean;var k,l:integer;begin pa:=true; for k:=1 to o do if f(c,listk) then pa:=false;end;遞歸輸出，按父結(jié)點是否為0來輸出procedure print(c:integer);begin if fac0 then print(fac); for i:=1 to 3 do begin fo

29、r j:=1 to 3 do write(listci,j, ); writeln; end; writeln;end;找0的位置以便于繼續(xù)擴展procedure fou;var k,l:integer;begin for k:=1 to 3 do for l:=1 to 3 do if listjk,l=0 then begin x:=k; y:=l; end;end;beginfor i:=1 to 3 do begin for j:=1 to 3 do begin read(list1i,j); end; readln; end; for i:=1 to 3 do begin for j

30、:=1 to 3 do read(bi,j); readln; end; o:=1;隊列初始化 j:=0; fa1:=0; while j0)and(y+ni,20)and(x+ni,14)and(y+ni,21000) then break; end; if found then print(o) else writeln(NO ANSWER);end.最少步數(shù)在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生設想：如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個19

31、19的圍棋的圍棋盤上任選兩點A，B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走。倆人一個走黑馬，一個走白馬。誰用最少的步數(shù)走到左上角坐標為（1，1）的點時，誰獲勝?，F(xiàn)在他請你幫忙，給你A，B兩點的坐標，想知道兩個位置到（1，1）點的可能的最少步數(shù)。輸入：12 1618 10輸出：89分析：由于A,B兩點是隨機輸入的，因此我們無法找到計算最少步數(shù)的數(shù)學規(guī)律，只能通過廣度優(yōu)先搜索的辦法求解。（1）確定出發(fā)點從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從（x,y）至棋盤上所有可達到的點的最少步數(shù)。而問題中要求的是黑馬所在的（x1,y1）和白馬所在的（x2,y2

32、）到達（1，1）目標點的最少步數(shù)。雖然兩條路徑的起點不同,但它們的終點卻是相同的。如果我們將終點（1，1）為起點，這樣只需要一次廣度搜索便可以得到（x1,y1）和（x2,x2）到達（1，1）的最小步數(shù)。（2）數(shù)據(jù)結(jié)構(gòu)設：que隊列，存儲從（1，1）可到達的點（quek，1.2）以及到達該點所需要的最小步數(shù)（quek，3）（0k192+1）。隊列的首指針為closed，尾指針為open。初始時，que中只有一個元素為（1，1），最少步數(shù)為0。s記錄（1，1）到每點所需的最少步數(shù)。顯然，問題的答案是sx1，y1和x2，y2 。初始時，s1，1為0，除此之外的所有元素的值均設為-1。為了使馬從棋盤內(nèi)

33、任意位置擴展出的坐標均在s的范圍內(nèi)，我們將s的數(shù)組的范圍擴大至s-1.21,-1.21。dx,dy移動后的位置增量數(shù)組。馬有12種不同的擴展方向：馬走“日”：(x-2,y-1),(x-1,y-2),(x-2,y+1),(x-1,y+2),(x+2,y-1),(x+1,y-2),(x+2,y+1),(x+1,y+2)。馬走“田”:(x-2,y-2),(x-2,y+2),(x+2,y-2),(x+2,y+2).我們將i方向上的位置增量存入常量數(shù)組dxi和dxi中（1i12）：Const dx:array1.12 of integer=(-2,-2-1,1,2,2,2,2,1,-1,-2,-2);

34、dy:array1.12 of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1);(3)約束條件不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴展過，且到達（1，1）最少需要0步”。這看上去是荒謬的，但是可以簡單而有效地避免馬再次落入這些界外點。該點在以前的擴展中沒有到達過。如果曾經(jīng)到達過，則根據(jù)廣度優(yōu)先搜索的的原理，先前到達該點所需的步數(shù)一定小于當前步數(shù)，因此完全沒有必要再擴展下去。由此得出，馬跳后的位置（x,y）是否可以入隊的約束條件是sx,y0。（4）算法流程 fillchar(s,sizeof(s)

35、,o);s1,1:=0; for x1:=1 to 19 do for y1:=1 to 19 do sx1,y1:=-1; open:=1;closed:=0; que1,1:=1;que1,2:=1; read(x1,y1,x2,y2); while closedopen do begin inc(closed); for d:=1 to 12 do begin x:=queclosed,1+dxd; y:=queclosed,2+dyd; if sx,y0 then begin sx,y:=queclosed,3+1; inc(open); queopen,1:=x;queopen,2:

36、=y;queopen,3:=sx,y; end; end; end; end; writeln(sx1,y1); writeln(sx2,y2);小鼠迷宮問題【問題描述】小鼠a與小鼠b身處一個mn的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這mn個房間中有一些房間是封閉的，不允許任何人進入。在迷宮中任何位置均可沿上，下，左，右4個方向進入未封閉的房間。小鼠a位于迷宮的（p，q）方格中，它必須找出一條通向小鼠b所在的（r，s）方格的路。請幫助小鼠a找出通向小鼠b的最短道路。 【輸入格式】輸入文件中的第一行為三個正整數(shù)n，m，k（1=n，m=100，0=k=mn-2），分別表示迷宮的行數(shù)，

37、列數(shù)和封閉的房間數(shù)。接下來的k行，每行有兩個正整數(shù)，表示被封閉的房間所在的行號和列號。最后的兩行，每行有兩個正整數(shù)，分別表示小鼠a所處的方格（p，q）和小鼠b所處的方格（r，s），小鼠a和小鼠b所處的方格是不封閉的?！据敵龈袷健枯敵鑫募袨橛嬎愠龅男∈骯通向小鼠b的最短路長度?！据斎胼敵鰳永枯斎耄海╩aze.in）：8 8 33 34 56 62 17 7輸出：（maze.out）：11源程序：const maxn=100;w:array1.4of integer=(1,0,-1,0);定義狀態(tài)變化u:array1.4of integer=(0,1,0,-1);var map:array1.