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

1、廣度優(yōu)先搜索 BFSBreadth-First-Search 1隊(duì)的定義： 隊(duì)是特殊的線性表之一，它只允許在隊(duì)的一端插入，在隊(duì)的另一端刪除。插入一端叫隊(duì)尾（T），刪除一端叫隊(duì)首（H），沒有任何元素的隊(duì)叫做空隊(duì)。隊(duì)列遵循先進(jìn)先出原則，排隊(duì)購物、買票等，就是最常見的隊(duì)。 2隊(duì)的定義：3隊(duì)的基本操作 隊(duì)的描述 int q10000;int h,t;初始化 h=t=1;注意此處q的變量類型，如果隊(duì)列元素信息用整數(shù)來表示此處就用int如果元素是一個(gè)坐標(biāo)則應(yīng)該int q100002;或者用結(jié)構(gòu)體4入隊(duì)操作 void enter(int x) qt=x; t+;把元素x入隊(duì)，放到隊(duì)尾5出隊(duì)操作 void o

2、ut() qh=0; h+;我們定義的h變量，qh的值就是隊(duì)首元素，通常我們使用完隊(duì)首元素后，隊(duì)首元素就應(yīng)該馬上出隊(duì)6注意隊(duì)列的風(fēng)格有很多種本文介紹的風(fēng)格是把t位置預(yù)留出來，也就是qt 永遠(yuǎn)是預(yù)留出來給下一個(gè)將要進(jìn)隊(duì)的元素當(dāng)前隊(duì)尾元素是qt-1;通常我們不會直接使用隊(duì)尾元素而qh直接等于隊(duì)首隊(duì)列長度直接等于(t-h)t=h的時(shí)候代表隊(duì)列為空7廣度優(yōu)先搜索 廣度優(yōu)先搜索類似于按層次遍歷的過程。它和隊(duì)有很多相似之處，運(yùn)用了隊(duì)的許多思想，其實(shí)就是對隊(duì)的深入一步研究，它的基本操作和隊(duì)列幾乎一樣。8舉一個(gè)例子從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個(gè)城市。問最少經(jīng)過多少城市9

3、例子方便大家理解，1表示能走，0表示不能走。這就是所謂鄰接矩陣 E100100;10我們使用隊(duì)列思想A為起點(diǎn)，最開始我們將A入隊(duì)，標(biāo)記A為”走過”我們定義一個(gè)數(shù)組z10000;如果zi為0則代表沒走過對于位于隊(duì)首的點(diǎn)，找出其直接相連而又沒有走過的點(diǎn)設(shè)隊(duì)首為qh用k循環(huán)一遍所有的點(diǎn)，看是否與A直接相連，又沒有走過if( E qh k =1&zk=0 )11if( E qh k =1&zk=0 )對于滿足要求的k，把k進(jìn)隊(duì)enter(k);并把點(diǎn)k標(biāo)記為“走過”zk=z qh +1;這樣zk肯定不會是0了K循環(huán)完了以后，隊(duì)首就沒用了，把它出隊(duì)out();1213141516171819202122

4、23242526272829#includeint i,j,k,l,m,n,a1000000;int E100100=1,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1,0;int q10000;int z10000;int h,t;void enter(int x) qt=x; t+;void out() qh=0; h+;main() z1=1; enter

5、(1); while(h!=t) for(k=1;k=8;k+) if(Ehqk=1&zk=0) enter(k); zk=zhq+1; out(); printf(%dn,z8); return 0;301188-Giroro說不準(zhǔn)遲到 這天開會，keroro又睡過頭了。一看鐘，離開會時(shí)間還有很短時(shí)間！必須在最短的時(shí)間內(nèi)到達(dá)會議室！ 現(xiàn)在我們假定他處在一個(gè)二維地圖上，其中keroro所在的坐標(biāo)是（0,0），然后地圖上有n個(gè)障礙物，即不能通過的點(diǎn)，坐標(biāo)為（x,y），（-500=x,y=500）。會議室的坐標(biāo)為（ex，ey），（-500=ex,ey=500）。在這個(gè)地圖上keroro每一步只能移

6、動相鄰的4個(gè)點(diǎn)的坐標(biāo)，且不穿直接穿過障礙物。如果他到達(dá)會議室的時(shí)間（即所走的步數(shù)）超過d（deadline），那么輸出-1，否則輸出keroro到達(dá)會議室所走的最少步數(shù)。假設(shè)至少存在一條路能到達(dá)會議室。311188-Giroro說不準(zhǔn)遲到Input 第一行為四個(gè)整數(shù)，n,d,ex,ey。(1=n=10000;0=d=1000;-500=ex,ey=500) 第2行到第n+1行，每行兩個(gè)整數(shù)x,y。(-500=x,y=500) Output 如果keroro遲到則輸出-1 ，否則輸出keroro到會議室所走最少的步數(shù)。Sample Input 7 101 2 0 2 -1 3 3 1 1 1 4

7、 2 -1 12 2 Sample Output -1 Hint 上述例子最少要11步，所以遲到了。32#includeint i,j,k,l,m,n,a10000;int c20002000;int q20000002,X,Y,z1,z2,z3,z4;int h,t;int fx42=0,1,0,-1,1,0,-1,0;void enter(int x,int y) qt0=x; qt1=y; t+;void out() qh0=0; qh0=0; h+;33main()scanf(%d%d%d%d,&n,&m,&X,&Y); X+=500,Y+=500; for(i=1;i=n;i+) scanf(%d%d,&j,&k); cj+500k+500=100000; enter(500,500); c500500=1; while(h!=t) z1=qh0; z2=qh1; for(k=0;k4;k+) z3=z1+fxk0; z4=z2+fxk1; if(cz3z4=