mutong在yj41上第20講隊(duì)列與廣搜

1、第三講 隊(duì)列與廣搜廣度優(yōu)先 搜索算法（bfs）:1、適合的題目類型： 1）、求從給定初始狀態(tài)到目標(biāo)狀態(tài)最少需要的步數(shù)。 2）、給定初始狀態(tài)，經(jīng)過k步后能夠到達(dá)哪些狀態(tài)。2、利用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列。3、狀態(tài)的最大值：決定隊(duì)列的大小（非常重要）4、隊(duì)列里需要記住哪些狀態(tài)：一般使用記錄數(shù)據(jù)類型。5、狀態(tài)的轉(zhuǎn)移：不能遺漏。6、狀態(tài)的判重：避免重復(fù)進(jìn)入隊(duì)列。7、無解的判斷head=0：隊(duì)列的首指針；tail=1：隊(duì)列的尾指針；Quene1:初始結(jié)點(diǎn);While headtail do /還有未擴(kuò)展的結(jié)點(diǎn)，隊(duì)列不空 Begin Inc（head）； /移動(dòng)隊(duì)列的首指針：出隊(duì)列 記錄head狀態(tài)； For i

2、=1 to method do /按規(guī)則擴(kuò)展下一層新的子結(jié)點(diǎn) if 條件滿足 then Begin 生成新的結(jié)點(diǎn); if 新結(jié)點(diǎn)隊(duì)列中沒出現(xiàn)過 then 保存新結(jié)點(diǎn)（入隊(duì)列）； if 新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then print(tail) 搜索結(jié)束； End End；Print(-1); /無解BFS的基本框架：If 新結(jié)點(diǎn)在隊(duì)列中沒出現(xiàn)過 then begin inc(tail); 新結(jié)點(diǎn)入隊(duì)； /必要時(shí)做標(biāo)記 if 新結(jié)點(diǎn)=目標(biāo) then print(tail); end；type queue=record 必要的有用的狀態(tài); father:longint;/父親結(jié)點(diǎn)，輸出路徑 depth:l

3、ongint; end;q:array1.maxn of queue;隊(duì)列的大小作為全局變量，避免用作局部變量，尤其當(dāng)maxn很多時(shí)。/輸出轉(zhuǎn)化過程：路線 procedure dfs(i:longint);/從當(dāng)前點(diǎn)遞歸輸出 begin if qi.father0 then dfs(qi.father); write(qi.v, ); end; procedure print(k:longint); begin writeln(qk.depth); dfs(k); halt; end;常用的判重方法：合適的布爾類型 (迷宮類)樸素的隊(duì)列查找 find(1.tail)：如果多，時(shí)間長構(gòu)造合適的哈

4、希函數(shù)：為了分類，減少查找時(shí)間影響bfs時(shí)間的關(guān)鍵：重點(diǎn)減少不必要的擴(kuò)展結(jié)點(diǎn)【問題描述】對于只含有字母A和B的字符串，給定初始串s1和目標(biāo)串s2。同時(shí)給定串中字母的移動(dòng)規(guī)則：每次移動(dòng)只能交換兩個(gè)相鄰的字母。任務(wù)：求s1最少經(jīng)過多少次交換得到s2?！据斎搿康谝恍校撼跏即畇1。第二行：目標(biāo)串s2?！据敵觥坑蓅1生成s2的最少交換次數(shù)?！緮?shù)據(jù)范圍限制】100%的數(shù)據(jù)：s1和s2長度=20。【輸入輸出樣例】 change.inchange.outAABBAABAAAAB44、A B交換保存的狀態(tài)狀態(tài)數(shù)量：隊(duì)列的大小狀態(tài)的擴(kuò)展條件判重方法分析：判重的改進(jìn)： 構(gòu)造哈希函數(shù)：把AB串對應(yīng)于二進(jìn)制A:0 B:

5、1AB串和二進(jìn)制一一對應(yīng)關(guān)系。AABBAA00110012。f12=true大?。?0位：220function hash(s:string):longint; var k,i:longint; begin k:=0; for i:=n downto 1 do k:=k*2+ord(si)-65; hash:=k; end;構(gòu)造函數(shù)：hash(s)fhash(s)=true head:=0; tail:=1; q1.str:=s1; q1.depth:=0; fhash(s1):=true; while headtail do begin inc(head); s:=qhead.str; st

6、ep:=qhead.depth; for i:=1 to n-1 do if sisi+1 then begin ss:=s; ssi:=si+1; ssi+1:=si; if not fhash(ss) then begin inc(tail); qtail.str:=ss; qtail.depth:=step+1; fhash(ss):=true; if ss=s2 then print(tail); end; end; end;構(gòu)造哈希函數(shù)的困難：如果ABC3個(gè)字母？幾進(jìn)制？26個(gè)小寫字母？多少進(jìn)制？ abc 數(shù)太大怎么辦？有時(shí)做不到一一對應(yīng)分類減少查找5、字符串變換AabcdBxyz變

7、換規(guī)則為：abc xu ud y y yzA=aayaayaa B=xyaayx變換規(guī)則：aa xy a拿規(guī)則去看看原串能否實(shí)現(xiàn)替換 n:=-1; while not eof do begin inc(n); readln(s); p:=pos( ,s); lan:=p-1; lbn:=length(s)-p; an:=copy(s,1,p-1); bn:=copy(s,p+1,lbn); end;一次變換能生成哪些？怎樣替換？ for i:=1 to n do/枚舉n個(gè)規(guī)則 for j:=1 to k-length(ai)+1 do if copy(s,j,lai)=ai then begi

8、n 生成新串； if not find(tem) then begin 入隊(duì)： 如果新串是目標(biāo)則輸出；停止； end; end; end;構(gòu)造哈希函數(shù)：把小寫字母看成29進(jìn)制？數(shù)太大，對1000000取模運(yùn)算function hash(s:string):longint; var k,i:longint; begin k:=0; for i:=1 to length(s) do begin k:=k*29+ord(si)-97; /k:=k*131+ord(si); k:=k mod 1000000; end; hash:=k; end; 有兩個(gè)無刻度標(biāo)志的水杯，分別可裝x升和y升的水。設(shè)另一

9、個(gè)水缸，可以用來向水杯灌水或從水杯向水缸里倒水，兩個(gè)水杯之間也可以相互倒水。已知x升的水杯開始是盛滿水的，y升的杯子是空的，問如何通過倒水和灌水操作，用最少的步數(shù)能在y升的杯子里量出z升水。6：倒水問題CA水缸（足夠的水,未滿）X=20 Y=15 Z=10Y=10？B輸入： 一行：x，y，z（0)and(by)。結(jié)果： 要么A空（ay-b）。 可以從A中倒mina,y-b升水給B。狀態(tài)： A：a-mina,y-b; B：b+mina,y-b。2: ACxax-ayby-bBAC條件： A中有水：a0結(jié)果： 把A中水全倒入C狀態(tài)： A: 0; B:b不變。3: BAxax-ayby-bBAC條件

10、：B中有水且A不滿，即 (b0)and(ax)。結(jié)果: 要么B空（bx-a）。 可以從B中倒minb,a-x升水給A。狀態(tài)：A：a+minb,x-a; B：b-minb,x-a。4: BCxax-ayby-bBAC條件： B中有水：b0結(jié)果: 把B中水全倒入C狀態(tài)： A: a ;B:0升。5: CAxax-ayby-bBAC條件： A不滿: ax。結(jié)果: 把A倒?jié)M狀態(tài)： A: x滿，B：b不變。6: CBxax-ayby-bBAC條件： B不滿：by。結(jié)果: 把B倒?jié)M狀態(tài)： A：a不變，B：y滿。算法實(shí)現(xiàn)：每倒一次需要保存的狀態(tài)：a,b,father,depth倒完一次后檢查：a和b的值：出現(xiàn)

11、 ? b=z ?隊(duì)列的大?。簃ax=100；（max+1）*（max+1）怎樣判斷重復(fù)： fi,j:boolean。A中出現(xiàn)i升，B中出現(xiàn)j升水的情況；Const max=100;type node=record a,b:integer; father:integer; depth:integer; /a:A中水；b：B中的水； end;var x,y,z:integer; q:array1.(max+1)*(max+1) of node; f:array0.max,0.max of boolean; /fi，j：A中i升水，B中j升水的情況是否出現(xiàn)過 head,tail:longint;bf

12、s fillchar(f,sizeof(f),false); head:=0; tail:=1; fx,0:=true; q1.a:=x; q1.b:=0; q1.father:=0; q1.depth:=0; while head0) and (bB check(a-min(a,y-b),b+min(a,y-b),step); if (a0) then check(0,b,step); / A-C if (b0) and (aA check(a+min(x-a,b),b-min(x-a,b),step); if (b0) then check(a,0,step); / B-C if (aA

13、if (bB end; print(-1); procedure check(i,j,d:integer);入隊(duì)列 begin if not fi,j then begin inc(tail); qtail.a:=i; qtail.b:=j; qtail.father:=head; qtail.depth:=d; fi,j:=true; if j=z then print(tail); end; end;輸出： procedure print(k:integer); procedure dfs(i:integer); begin if qi.father1 then dfs(qi.father

14、); writeln(qi.a, ,qi.b);/初始狀態(tài)不輸出 end; begin assign(output,fout);rewrite(output); if k=-1 then writeln(no answer) else begin writeln(qk.depth);dfs(k);end; close(output); halt; end;7、最短編號序列 初始狀態(tài)保存信息結(jié)點(diǎn)擴(kuò)展條件【問題描述：】在n*n的棋盤上有一匹馬在第x行第y列的格子上。棋盤上有些格子上有障礙物，馬不能達(dá)到有障礙物的格子。已知馬在棋盤中的走法按“日“字8個(gè)方向可走，如下圖所示：問：哪些格子能到達(dá)，到達(dá)這

15、些格子的最小步數(shù)是多少?！据斎耄骸康谝恍?n（n=100）,x,y(馬的開始位置)。接下來n行為棋盤的描述：“-“為空格子，”+“表示該格子有障礙物?！据敵觯骸縩行，每行n個(gè)用空格隔開的數(shù)，表示馬到達(dá)該格子的最少步數(shù)，如果無法到達(dá)則用-1表示。4、馬的遍歷4 2 2-+-【樣例輸入：】4 3 2 13 0 3 22 3 -1 11 2 1 4【樣例輸出：】11112222333344 dx:array1.8 of integer=(-1,-2,-2,-1,1,2,2,1); dy:array1.8 of integer=(2,1,-1,-2,-2,-1,1,2);var can:array-1

16、.maxn+2,-1.maxn+2 of boolean; dist:array1.maxn,1.maxn of integer; /記錄最少步數(shù) q:array1.maxn*maxn,1.2 of integer; head,tail:longint； procedure init; var s:string; begin readln(n,x0,y0); fillchar(can,sizeof(can),false); for i:=1 to n do begin readln(s); for j:=1 to n do cani,j:=sj=-; end; end;procedure bf

17、s;/廣度優(yōu)先搜索 begin for i:=1 to n do for j:=1 to n do disti,j:=-1; head:=0; tail:=1; / 隊(duì)列初始化 distx0,y0:=0; q1,1:=x0; q1,2:= y0; / 起點(diǎn)進(jìn)隊(duì)列 while headtail do begin inc(head); /出隊(duì)列 x:=qhead,1; y:=qhead,2; /記錄出隊(duì)結(jié)點(diǎn)狀態(tài) for k:=1 to 8 do /擴(kuò)張結(jié)點(diǎn)：走下一步 begin xx:=x+dxk; yy:=y+dyk; if canxx,yy and (distxx,yy=-1) then /能

18、走但沒走過 begin distxx,yy:=distx,y+1; inc(tail); qtail,1:=xx; qtail,2:=yy; end; end; end; end;5、最少轉(zhuǎn)彎次數(shù) 給出一張地圖，這張地圖被分成n*m個(gè)方塊任何一個(gè)方塊不是高山就是平地。平地可以通過，而高山不安可以通過，現(xiàn)在，你處在地圖的A（x1，y1）這塊平地上，問：你至少需要拐幾個(gè)彎才能到達(dá)目的地B（x2，y2）。如上圖中（黑色是高山），（x1，y1）到（x2，y2）至少轉(zhuǎn)5個(gè)彎。輸入：第一行：n，m（=100）第二行：x1，y1，x2，y2（=100）以下n行m列的矩陣，0代表高山，1代表平地。中間空格隔開

19、。輸出：最少拐彎次數(shù)。樣例：輸入：5 71 3 1 70 1 1 1 1 0 11 1 0 1 0 1 11 1 1 1 0 1 01 0 0 1 1 1 11 1 1 1 0 0 1輸出：5分析：關(guān)鍵點(diǎn)： 1)、從某一位置出發(fā)，在一個(gè)方向上到達(dá)的點(diǎn)不再需要拐彎。沿某個(gè)方向能走就走，直到遇到高山為止。所以： 2）、從起始點(diǎn)（x1，y1）出發(fā)能到達(dá)他的4個(gè)方向上的所有點(diǎn)。不需要拐彎。這些點(diǎn)的拐彎數(shù)都是0。 3）、走過的地方做標(biāo)記，不能與平地和高山用一個(gè)標(biāo)記？遇到已經(jīng)走過的格子，只要前面不是高山可以繼續(xù)往前走。type node=record x,y:integer; depth:integer; end;var q:array1.maxn*maxn of node;隊(duì)列數(shù)據(jù)庫 can:array0.maxn+1,0.maxn+1 of boolea