mutong在yj41上第20讲队列与广搜

1、第三讲 队列与广搜广度优先 搜索算法（bfs）:1、适合的题目类型： 1）、求从给定初始状态到目标状态最少需要的步数。 2）、给定初始状态，经过k步后能够到达哪些状态。2、利用的数据结构：队列。3、状态的最大值：决定队列的大小（非常重要）4、队列里需要记住哪些状态：一般使用记录数据类型。5、状态的转移：不能遗漏。6、状态的判重：避免重复进入队列。7、无解的判断head=0：队列的首指针；tail=1：队列的尾指针；Quene1:初始结点;While headtail do /还有未扩展的结点，队列不空 Begin Inc（head）； /移动队列的首指针：出队列 记录head状态； For i

2、=1 to method do /按规则扩展下一层新的子结点 if 条件满足 then Begin 生成新的结点; if 新结点队列中没出现过 then 保存新结点（入队列）； if 新结点是目标结点 then print(tail) 搜索结束； End End；Print(-1); /无解BFS的基本框架：If 新结点在队列中没出现过 then begin inc(tail); 新结点入队； /必要时做标记 if 新结点=目标 then print(tail); end；type queue=record 必要的有用的状态; father:longint;/父亲结点，输出路径 depth:l

3、ongint; end;q:array1.maxn of queue;队列的大小作为全局变量，避免用作局部变量，尤其当maxn很多时。/输出转化过程：路线 procedure dfs(i:longint);/从当前点递归输出 begin if qi.father0 then dfs(qi.father); write(qi.v, ); end; procedure print(k:longint); begin writeln(qk.depth); dfs(k); halt; end;常用的判重方法：合适的布尔类型 (迷宫类)朴素的队列查找 find(1.tail)：如果多，时间长构造合适的哈

4、希函数：为了分类，减少查找时间影响bfs时间的关键：重点减少不必要的扩展结点【问题描述】对于只含有字母A和B的字符串，给定初始串s1和目标串s2。同时给定串中字母的移动规则：每次移动只能交换两个相邻的字母。任务：求s1最少经过多少次交换得到s2。【输入】第一行：初始串s1。第二行：目标串s2。【输出】由s1生成s2的最少交换次数。【数据范围限制】100%的数据：s1和s2长度=20。【输入输出样例】 change.inchange.outAABBAABAAAAB44、A B交换保存的状态状态数量：队列的大小状态的扩展条件判重方法分析：判重的改进： 构造哈希函数：把AB串对应于二进制A:0 B:

5、1AB串和二进制一一对应关系。AABBAA00110012。f12=true大小：20位：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;构造函数：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;构造哈希函数的困难：如果ABC3个字母？几进制？26个小写字母？多少进制？ abc 数太大怎么办？有时做不到一一对应分类减少查找5、字符串变换AabcdBxyz变

7、换规则为：abc xu ud y y yzA=aayaayaa B=xyaayx变换规则：aa xy a拿规则去看看原串能否实现替换 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个规则 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 入队： 如果新串是目标则输出；停止； end; end; end;构造哈希函数：把小写字母看成29进制？数太大，对1000000取模运算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; 有两个无刻度标志的水杯，分别可装x升和y升的水。设另一

9、个水缸，可以用来向水杯灌水或从水杯向水缸里倒水，两个水杯之间也可以相互倒水。已知x升的水杯开始是盛满水的，y升的杯子是空的，问如何通过倒水和灌水操作，用最少的步数能在y升的杯子里量出z升水。6：倒水问题CA水缸（足够的水,未满）X=20 Y=15 Z=10Y=10？B输入： 一行：x，y，z（0)and(by)。结果： 要么A空（ay-b）。 可以从A中倒mina,y-b升水给B。状态： A：a-mina,y-b; B：b+mina,y-b。2: ACxax-ayby-bBAC条件： A中有水：a0结果： 把A中水全倒入C状态： A: 0; B:b不变。3: BAxax-ayby-bBAC条件

10、：B中有水且A不满，即 (b0)and(ax)。结果: 要么B空（bx-a）。 可以从B中倒minb,a-x升水给A。状态：A：a+minb,x-a; B：b-minb,x-a。4: BCxax-ayby-bBAC条件： B中有水：b0结果: 把B中水全倒入C状态： A: a ;B:0升。5: CAxax-ayby-bBAC条件： A不满: ax。结果: 把A倒满状态： A: x满，B：b不变。6: CBxax-ayby-bBAC条件： B不满：by。结果: 把B倒满状态： A：a不变，B：y满。算法实现：每倒一次需要保存的状态：a,b,father,depth倒完一次后检查：a和b的值：出现

11、 ? b=z ?队列的大小：max=100；（max+1）*（max+1）怎样判断重复： fi,j:boolean。A中出现i升，B中出现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升水的情况是否出现过 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);入队列 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);/初始状态不输出 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、最短编号序列 初始状态保存信息结点扩展条件【问题描述：】在n*n的棋盘上有一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：问：哪些格子能到达，到达这

15、些格子的最小步数是多少。【输入：】第一行:n（n=100）,x,y(马的开始位置)。接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。【输出：】n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-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; /记录最少步数 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;/广度优先搜索 begin for i:=1 to n do for j:=1 to n do disti,j:=-1; head:=0; tail:=1; / 队列初始化 distx0,y0:=0; q1,1:=x0; q1,2:= y0; / 起点进队列 while headtail do begin inc(head); /出队列 x:=qhead,1; y:=qhead,2; /记录出队结点状态 for k:=1 to 8 do /扩张结点：走下一步 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、最少转弯次数 给出一张地图，这张地图被分成n*m个方块任何一个方块不是高山就是平地。平地可以通过，而高山不安可以通过，现在，你处在地图的A（x1，y1）这块平地上，问：你至少需要拐几个弯才能到达目的地B（x2，y2）。如上图中（黑色是高山），（x1，y1）到（x2，y2）至少转5个弯。输入：第一行：n，m（=100）第二行：x1，y1，x2，y2（=100）以下n行m列的矩阵，0代表高山，1代表平地。中间空格隔开

19、。输出：最少拐弯次数。样例：输入：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分析：关键点： 1)、从某一位置出发，在一个方向上到达的点不再需要拐弯。沿某个方向能走就走，直到遇到高山为止。所以： 2）、从起始点（x1，y1）出发能到达他的4个方向上的所有点。不需要拐弯。这些点的拐弯数都是0。 3）、走过的地方做标记，不能与平地和高山用一个标记？遇到已经走过的格子，只要前面不是高山可以继续往前走。type node=record x,y:integer; depth:integer; end;var q:array1.maxn*maxn of node;队列数据库 can:array0.maxn+1,0.maxn+1 of boolea