廣度寬度優(yōu)先搜索

廣度寬度優(yōu)先搜索第一頁，共三十九頁，2022年，8月28日深度搜索與廣度搜索區(qū)分[深度搜索與廣度搜索]深度搜索與廣度搜索的區(qū)別：深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來的子節(jié)點中的一個，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點的兄弟節(jié)點。在具體實現(xiàn)上為了提高效率,所以采用了不同的數(shù)據(jù)結(jié)構(gòu)。廣度搜索是求解最優(yōu)解的一種較好的方法，而深度搜索多用于只要求解，并且解答樹中的重復(fù)節(jié)點較多并且重復(fù)較難判斷時使用，但往往可以用回溯算法代替。第二頁，共三十九頁，2022年，8月28日一些基本概念節(jié)點：記錄擴(kuò)展的狀態(tài)。弧/邊：記錄擴(kuò)展的路徑。搜索樹：描述搜索擴(kuò)展的整個過程。節(jié)點的耗散值 令C(i,j)為從節(jié)點ni到nj的這段路徑（或者弧）的耗散值,一條路徑的耗散值就等于連接這條路徑各節(jié)點間所有弧的耗散值總和?？梢杂眠f歸公式描述如下：

C(ni,t)=C(ni,nj)+C(nj,t)4搜索樹根節(jié)點葉子節(jié)點4,5,6,7,88123567第三頁，共三十九頁，2022年，8月28日廣度優(yōu)先搜索的過程

廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。廣度優(yōu)先算法的核心思想是：從初始節(jié)點開始，應(yīng)用算符生成第一層節(jié)點，檢查目標(biāo)節(jié)點是否在這些后繼節(jié)點中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點逐一擴(kuò)展，得到第二層節(jié)點，并逐一檢查第二層節(jié)點中是否包含目標(biāo)節(jié)點。若沒有，再用算符逐一擴(kuò)展第二層的所有節(jié)點……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點為止。即⒈從圖中的某一頂點V0開始，先訪問V0；⒉訪問所有與V0相鄰接的頂點V1，V2，......，Vt；⒊依次訪問與V1，V2，......，Vt相鄰接的所有未曾訪問過的頂點；⒋循此以往，直至所有的頂點都被訪問過為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長的趨勢，所以稱之為廣度優(yōu)先搜索。第四頁，共三十九頁，2022年，8月28日廣度搜索策略綜合數(shù)據(jù)庫（變量設(shè)置）

與問題相關(guān)的所有數(shù)據(jù)元素構(gòu)成的集合，用來表述問題狀態(tài)或有關(guān)事實。產(chǎn)生式規(guī)則 構(gòu)建了綜合數(shù)據(jù)庫以后，還需要研究問題的移動規(guī)則，稱為產(chǎn)生式規(guī)則。搜索策略 搜索策略的實質(zhì)是確定如何選取規(guī)則的方式。有兩種基本方式：一種是不考慮給定問題所具有的特定知識，系統(tǒng)根據(jù)事先確定好某種固定順序，依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則，這實際上是盲目搜索的方法。另一種是考慮問題領(lǐng)域可應(yīng)用的知識，動態(tài)地確定規(guī)則的排列次序，優(yōu)先調(diào)用較合適的規(guī)則使用，這就是通常所說的啟發(fā)式搜索策略。第五頁，共三十九頁，2022年，8月28日廣度優(yōu)先搜索算法描述：Programbfs；初始化，初始狀態(tài)存入隊列；隊列首指針head:=0;尾指針tail:=1；repeat

指針head后移一位，指向待擴(kuò)展結(jié)點；

fori:=1tomaxdobegin//max為產(chǎn)生子結(jié)點的規(guī)則數(shù)if子結(jié)點符合條件thenbegintail指針增1，把新結(jié)點存入列尾；

if新結(jié)點與原已產(chǎn)生結(jié)點重復(fù)then刪去該結(jié)點（取消入隊，tail減1）

elseif新結(jié)點是目標(biāo)結(jié)點then輸出并退出；end;end;until(head>=tail);//隊列為空第六頁，共三十九頁，2022年，8月28日廣度優(yōu)先搜索注意事項1、每生成一個子結(jié)點，就要提供指向它們父親結(jié)點的指針。當(dāng)解出現(xiàn)時候，通過逆向跟蹤，找到從根結(jié)點到目標(biāo)結(jié)點的一條路徑。當(dāng)然不要求輸出路徑，就沒必要記父親。

2、生成的結(jié)點要與前面所有已經(jīng)產(chǎn)生結(jié)點比較，以免出現(xiàn)重復(fù)結(jié)點，浪費時間，還有可能陷入死循環(huán)。

3、如果目標(biāo)結(jié)點的深度與“費用”（如：路徑長度）成正比，那么，找到的第一個解即為最優(yōu)解，這時，搜索速度比深度搜索要快些，在求最優(yōu)解時往往采用廣度優(yōu)先搜索；如果結(jié)點的“費用”不與深度成正比時，第一次找到的解不一定是最優(yōu)解。

4、廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點所在位置情況，如果目標(biāo)結(jié)點深度處于較深層時，需搜索的結(jié)點數(shù)基本上以指數(shù)增長。第七頁，共三十九頁，2022年，8月28日八數(shù)碼問題

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

下面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹。搜索樹上的所有結(jié)點都標(biāo)記它們所對應(yīng)的狀態(tài)，每個結(jié)點旁邊的數(shù)字表示結(jié)點擴(kuò)展的順序。粗線條路徑表明求得的一個解。從圖中可以看出，擴(kuò)展第２６個結(jié)點，總共生成４６個結(jié)點之后，才求得這個解。此外，直接觀察此圖表明，不存在有更短走步序列的解。第八頁，共三十九頁，2022年，8月28日八數(shù)碼問題擴(kuò)展搜索樹

第九頁，共三十九頁，2022年，8月28日綜合數(shù)據(jù)庫（變量設(shè)置）{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

用Pascal語言描述如下：typet8no=array[1..3,1..3]oflongint;{棋盤狀態(tài)}tList=record{描述一個節(jié)點}Father:longint;

{父指針}dep:longint;

{深度}x,y:longint; {空格的位置}state:t8no;

end;const

Max=10000;vars,t:t8no;{s為初始狀態(tài)，t為目標(biāo)狀態(tài)}List:array[0..max]oftList;{綜合數(shù)據(jù)庫}第十頁，共三十九頁，2022年，8月28日產(chǎn)生式規(guī)則（關(guān)系）if條件then規(guī)則；設(shè)Pxy表示將牌第x行第y列的數(shù)碼，m,n表示數(shù)碼空格所在的行列值，記Pm,n=0,則可以得到如下四條規(guī)則：

①ifn-1>=1thenbeginPm,n:=Pm,n-1-

;Pm,n-1-

-:=0end;②ifm-1>=1thenbeginPm,n:=Pm-1,n;Pm-1,n:=0end;③ifn+1<=3thenbeginPm,n:=Pm,n+1;Pm,n+1:=0end;④ifm+1<=3thenbeginPm,n:=Pm+1-,n;Pm+1-,n:=0end;ConstDir:array[1..4,1..2]oflongint{對應(yīng)四種產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));第十一頁，共三十九頁，2022年，8月28日控制策略

PROCEDUREProduction-System；DATA初始化數(shù)據(jù)庫Repeat

在規(guī)則集中選擇某一條可作用于DATA的規(guī)則R

DATAR作用于DATA后得到的結(jié)果

UntilDATA滿足結(jié)束條件第十二頁，共三十九頁，2022年，8月28日八數(shù)碼問題寬度優(yōu)先算法框架List[1]=source;closed:=0;open:=1;{加入初始節(jié)點,List為擴(kuò)展節(jié)點的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed對應(yīng)的節(jié)點}Forx:=1to4dobeginnew:=move(n,4);{對n節(jié)點使用第x條規(guī)則，得到new}ifnot_appear(new,List)thenbegin{如果new沒有在List中出現(xiàn)}open:=open+1;List[open]:=new;{加入新節(jié)點到open}List[open].Father:=closed;{修改指針}ifList[open]=GoalthenGetOut;end;enduntilclosed<open;第十三頁，共三十九頁，2022年，8月28日八數(shù)碼參考程序（寬度優(yōu)先）program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}Constdir:array[1..4,1..2]oflongint

{四種移動方向，對應(yīng)產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]oflongint;TList=recordFather:longint;

{父指針}dep:longint;

{深度}X0,Y0:longint; {0的位置}State:T8no;

{棋盤狀態(tài)}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}Closed,open,Best:integer{Best表示最優(yōu)移動次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標(biāo)志}第十四頁，共三十九頁，2022年，8月28日procedureGetInfo;{讀入初始和目標(biāo)節(jié)點}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}varx,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;第十五頁，共三十九頁，2022年，8月28日functionnot_Appear(new:tList):boolean;{判斷new是否在List中出現(xiàn)}vari:integer;beginnot_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;not_Appear:=true;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{將第d條規(guī)則作用于n得到new,OK是new是否可行的標(biāo)志}varx,y:integer;beginX:=n.x0+Dir[d,1];Y:=n.y0+Dir[d,2];{判斷new的可行性}ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok:=false;exitend;OK:=true;FunctionSame(A,B:T8no):Boolean;{判斷A,B狀態(tài)是否相等}Vari,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]<>B[i,j]thenexit;Same:=true;End;第十六頁，共三十九頁，2022年，8月28日new.State:=n.State;{new=Expand(n,d)}new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedureAdd(new:tList);{插入節(jié)點new}beginifnot_Appear(new)thenBegin{如果new沒有在List出現(xiàn)}Inc(open);{new加入open表}List[open]:=new;end;end;第十七頁，共三十九頁，2022年，8月28日procedureExpand(Index:integer;varn:tList);{擴(kuò)展n的子節(jié)點}vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４條規(guī)則}Move(n,i,OK,new);ifnotokthencontinue;new.Father:=Index;new.Dep:=n.dep+1;Add(new);end;end;

第十八頁，共三十九頁，2022年，8月28日procedureGetOutInfo;{輸出}procedureOutlook(Index:integer);{遞歸輸出每一個解}vari,j:integer;beginifIndex=0thenexit;Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');writeln;end;writeln;end;beginWriteln('Total=',Best);Outlook(Answer);end;第十九頁，共三十九頁，2022年，8月28日procedureMain;{搜索主過程}beginRepeatInc(Closed);Expand(Closed,List[Closed]);{擴(kuò)展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{無解}end;beginAssign(Input,'input.txt');ReSet(Input);Assign(Output,'Output.txt');ReWrite(Output);GetInfo;Initialize;Main;Close(Input);Close(Output);End.第二十頁，共三十九頁，2022年，8月28日【例1】圖4表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個城市。現(xiàn)要找出一條經(jīng)過城市最少的一條路線。第二十一頁，共三十九頁，2022年，8月28日【算法分析】看到這圖很容易想到用鄰接距陣來表示，0表示能走，1表示不能走。如圖。

首先想到的是用隊列的思想。a數(shù)組是存儲擴(kuò)展結(jié)點的隊列，a[i].city記錄經(jīng)過的城市,a[i].pre記錄前趨城市，這樣就可以倒推出最短線路。具體過程如下：（1）將城市A入隊，隊首為0、隊尾為1。（2）將隊首所指的城市所有可直通的城市入隊（如果這個城市在隊列中出現(xiàn)過就不入隊，可用一個集合來判斷），將入隊城市的pre指向隊首的位置。然后將隊首加1，得到新的隊首城市。重復(fù)以上步驟，直到搜到城市H時，搜索結(jié)束。利用pre可倒推出最少城市線路。第二十二頁，共三十九頁，2022年，8月28日【參考程序】ProgramEx8_1;constju:array[1..8,1..8]of0..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));

typenode=record//記錄定義

city:char;

pre:integer;

end;

varhead,tail,i:integer;

a:array[1..100]ofnode;

s:setof'A'..'H';procedureout(d:integer);//輸出過程

begin

write(a[d].city);repeat

d:=a[d].pre;write('--',a[d].city);

untila[d].pre=0;

writeln;

end;第二十三頁，共三十九頁，2022年，8月28日proceduredoit;

begin

head:=0;tail:=1;

a[1].city:=‘A’;

a[1].pre:=0;

s:=[‘A’];

repeat//步驟2

inc(head);//隊首加一，出隊

fori:=1to8do//搜索可直通的城市

if（ju[ord(a[head].city)-64,i]=0）and（not（chr（i+64）ins））thenbegin//判斷城市是否走過

inc(tail);//隊尾加一，入隊

a[tail].city:=chr(64+i);

a[tail].pre:=head;

s:=s+[a[tail].city];

ifa[tail].city='H'thenbeginout[tail];break;end;

end;

untilhead=tail;

end;BEGIN//主程序doit;END.輸出：

H--F--A第二十四頁，共三十九頁，2022年，8月28日【例2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個數(shù)。如:陣列4100234500067103456050020456006710000000089有4個細(xì)胞?！舅惴ǚ治觥竣艔奈募凶x入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；

⑵沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個細(xì)胞；

⑶將細(xì)胞的位置入隊h，并沿其上、下、左、右四個方向上的細(xì)胞位置入隊，入隊后的位置bz數(shù)組置為FLASE；⑷將h隊的隊頭出隊，沿其上、下、左、右四個方向上的細(xì)胞位置入隊，入隊后的位置bz數(shù)組置為FLASE；

⑸重復(fù)4，直至h隊空為止，則此時找出了一個細(xì)胞；

⑹重復(fù)2，直至矩陣找不到細(xì)胞；

⑺輸出找到的細(xì)胞數(shù)。

第二十五頁，共三十九頁，2022年，8月28日programEx8_2;constdx:array[1..4]of-1..1=(-1,0,1,0);

dy:array[1..4]of-1..1=(0,1,0,-1);

varname,s:string;

pic:array[1..50,1..79]ofinteger;

bz:array[1..50,1..79]ofboolean;

m,n,i,j,num:integer;

h:array[1..4000,1..2]ofinteger;

proceduredoit(p,q:integer);

vari,t,w,x,y:integer;

begin

inc(num);bz[p,q]:=false;

t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;//遇到的第一個細(xì)胞入隊

repeat

fori:=1to4do//沿細(xì)胞的上下左右四個方向搜索細(xì)胞

begin

x:=h[t,1]+dx[i];y:=h[t,2]+dy[i];

if(x>0)and(x<=m)and(y>0)and(y<=n)andbz[x,y]

thenbegininc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;end;//本方向搜索到細(xì)胞就入隊

inc(t);//隊頭指針加1untilt>w;//直至隊空為止

end;第二十六頁，共三十九頁，2022年，8月28日begin

fillchar(bz,sizeof(bz),true);num:=0;readln(m,n);

fori:=1tomdo

beginreadln(s);

forj:=1tondo

beginpic[i,j]:=ord(s[j])-ord(‘0’);

ifpic[i,j]=0thenbz[i,j]:=false;

end;

end;

fori:=1tomdoforj:=1tondoifbz[i,j]thendoit(i,j);//在矩陣中尋找細(xì)胞

writeln('NUMBERofcells=',num);readln;end.第二十七頁，共三十九頁，2022年，8月28日【例3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號表示關(guān)卡?，F(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲如下圖6：請設(shè)計一種能從存儲數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法。第二十八頁，共三十九頁，2022年，8月28日【算法分析】

該題是一個路徑搜索問題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組NO存儲各關(guān)卡號，用數(shù)組PRE存儲訪問到某關(guān)卡號的前趨關(guān)卡號。其實本題是一個典型的圖的遍歷問題，我們可以采用圖的廣度優(yōu)先遍歷，并利用隊列的方式存儲頂點之間的聯(lián)系。從入口（1）開始先把它入隊，然后把（1）的所有關(guān)聯(lián)頂點都入隊，即訪問一個頂點，將其后繼頂點入隊，并存儲它的前趨頂點，……，直到訪問到出口（17）。最后，再從出口的關(guān)卡號（17）開始回訪它的前趨關(guān)卡號，……，直到入口的關(guān)卡號（1），則回訪的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號（17）的被訪問路徑最短的是：（17）←（16）←（19）←（18）←（1）由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下：假設(shè)用鄰接矩陣存放路線圖（a[I,j]=1表示I與j連通，a[I,j]=0表示I與j不連通）。再設(shè)一個隊列和一個表示拓展到哪個頂點的指針變量pos。（1）從入口開始，先把（1）入隊，并且根據(jù)鄰接矩陣，把（1）的后繼頂點全部入隊，并存儲這些后繼頂點的前趨頂點為（1）；再把pos后移一個，繼續(xù)拓展它，將其后繼頂點入隊，并存儲它們的前趨頂點，……，直到拓展到出口（目的地（17））；

第二十九頁，共三十九頁，2022年，8月28日

注意后繼頂點入隊前，必須要檢查這個頂點是否已在隊列中，如果已經(jīng)在了就不要入隊了；這一步可稱為圖的遍歷或拓展；（2）從隊列的最后一個關(guān)卡號（出口（17））開始，依次回訪它的前驅(qū)頂點，倒推所得到的路徑即為最短路徑。主要是依據(jù)每個頂點的前趨頂點倒推得到的。實現(xiàn)如下：

I：=1；

WHILENO[I]<>17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；【參考程序】留給同學(xué)們完成，文件名ex8_3.pas。第三十頁，共三十九頁，2022年，8月28日【例4】迷宮問題如下圖所示，給出一個N*M的迷宮圖和一個入口、一個出口。編一個程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個方向走。如果無路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個經(jīng)典的回溯算法問題，本例給出了回溯（深搜）程序和廣搜程序。實現(xiàn)見參考程序。第三十一頁，共三十九頁，2022年，8月28日【深搜參考程序】programEX8_4_1;constmaxn=50;varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,totstep:integer;route:array[1..maxn]ofrecordx,y:integer;end;proceduremove(x,y,step:integer);beginmap[x,y]:=step;//走一步，作標(biāo)記，把步數(shù)記下來

route[step].x:=x;route[step].y:=y;//記路徑

if(x=desx)and(y=desy)thenbeginf:=true;totstep:=step;endelsebeginif(y<>m)and(map[x,y+1]=0)thenmove(x,y+1,step+1);//向右

ifnotfand(x<>n)and(map[x+1,y]=0)thenmove(x+1,y,step+1);//往下

ifnotfand(y<>1)and(map[x,y-1]=0)thenmove(x,y-1,step+1);//往左

ifnotfand(x<>1)and(map[x-1,y]=0)thenmove(x-1,y,step+1);//往上

end;end;第三十二頁，共三十九頁，2022年，8月28日BEGINreadln(n,m);//n行m列的迷宮

fori:=1tondo//讀入迷宮，0表示通，-1表示不通

beginforj:=1tomdoread(map[i,j]);readln;end;write('inputtheenter:');readln(soux,souy);//入口

write('inputtheexit:');readln(desx,desy);//出口

f:=false;//f=false表示無解；f=true表示找到了一個解

move(soux,souy,1);iffthenfori:=1tototstepdo //輸出直迷宮的路徑

write(route[i]:4);elsewriteln('noway.');END.第三十三頁，共三十九頁，2022年，8月28日【廣搜參考程序】programEX8_4_2;constmaxn=50;u:array[1..4]ofinteger=(0,1,0,-1);w:array[1..4]ofinteger=(1,0,-1,0);varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,head,tail,x,y:integer;route:array[1..maxn]ofrecordx,y,pre:integer;end;procedureprint(d:integer);beginifroute[d].pre<>0thenprint(route[d].pre);write('(',route[d].x,',',route[d].y,')');end;BEGINreadln(n,m);//n行m列的迷宮

fori:=1tondo//讀入迷宮，0表示通，-1表示不通

beginforj:=1tomdoread(map[i,j]);readln;end;write('inputtheenter:');readln(soux,souy);//入口第三十四頁，共三十九頁，2022年，8月28日write('inputtheexit:');readln(desx,desy);//出口

head:=0;tail:=1;f:=false;map[soux,souy]:=-1;route[tail].x:=soux;route[tail].y:=souy;route[tail].pre:=0;whilehead<>taildo //隊列不為空

begininc(head);fori:=1to4do //4個方向

beginx:=route[head].x+u[i];y:=route[head].y+w[i];if(x>0)and(x<=n)and(y>0)and(y<=m)and(map[x,y]=0) then begin //本方向上可以走

inc(tail);route[tail].x:=x;route[tail].y:=y;route[tail].pre:=head;map[x,y]:=-1;if(x=desx)and(y=desy)then //擴(kuò)展出的結(jié)點為目標(biāo)結(jié)點

beginf:=true;print(tail);break;end;end;end;iffthenbreak;end;ifnotfthenwriteln('noway!');END.第三十五頁，共三十九頁，2022年，8月28日輸入1：輸出1：輸入2