队列与广搜（凤山书屋）

1、队列与广度优先搜索1阳山书屋队2阳山书屋规定：只能从队首出队只能从队尾入队每个人只能进出队一次3阳山书屋一 、队列的概念队列是一种的线性表，删除在表头（队头），插入在表尾（队尾）进行。先进先出（First In First Out）假设入队的顺序是：a1,a2,an， 则出队列的顺序也是： a1,a2,an。a1 a2 a3 an队头队尾出队列入队列4阳山书屋队尾：tail （指向队尾，最后一个元素）队首：head (习惯指向队首的前一位置，空的位置)队列数组q下标： 3 4 5 6 7 初始：head=tail=0非空： head=tail ;65419Headtail5阳山书屋定义：Con

2、st max=队列的大小；Var queue:array1.max of datatype; head,tail: longint;队列的两种操作： 入队：procedure add(x); 出队：function deldatatype=record data:各种需要保存状态 depth:longint; / 深度End;6阳山书屋1）、过程ADD(x)在队列q的尾端插入元素x procedure ADD( x：qtyper)； begin inc(tail); qtail：=x； end；ADD2）、函数DEL取出q队列的队首元素 function DEL； begin inc(head

3、); del:=qhead； end；DEL7阳山书屋二、广度优先搜索BFS (Breadth First Serach)也称为宽度优先搜索按层遍历的一种搜索方法8阳山书屋 深度优先搜索(Depth-First Search) dfs状态空间图 状态搜索树：先扩展最左边的结点，再扩展右边的结点 目标9阳山书屋 广度优先搜索(Breadth -First Search) bfs状态空间图 状态搜索树：先扩展深度小的结点，从上而下扩展结点 目标10阳山书的遍历(输出结点)：深度优先遍历（dfs）原则：能向前走就走，不能走就后退一步再选择可行点11阳山书屋a:array1.

4、maxn,1.maxn of integer;/邻接矩阵visited:array1.maxn of boolean; /访问标志procedure dfs(i:integer); /深度优先遍历结点 var j:integer; begin write(i, ); visitedi:=true; for j:=1 to n do if (ai,j=1)and(not visitedj) then dfs(j); end;begin init; dfs(1);end.12阳山书屋广度优先遍历（bfs）1搜索过程如下： 从起点开始由近及远按层次遍历。1435678291013阳山书屋 /q:ar

5、ray1.maxn of longint;/队列保存结点 head:=0; tail:=1; /队列初始化 q1:=1; visited1:=true; /1进队列，避免重复 while headtail do /队列不空 begin inc(head); /出队列 k:=qhead; write(k, ); for j:=1 to n do /找没有遍历过的邻接点 if (ak,j=1)and(visitedj=false) then begin inc(tail); /进队列 qtail:=j; visitedj:=true; end; end;14阳山书屋【问题描述：】在n*n的棋盘上有

6、一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：问：哪些格子能到达，到达这些格子的最小步数是多少。【输入：】第一行:n（n=100）,x,y(马的开始位置)。接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。【输出：】n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-1表示。1、跳马15阳山书屋4 2 2-+-【样例输入：】4 3 2 13 0 3 22 3 -1 11 2 1 4【样例输出：】马1111222233334416阳山书屋 dx:array1.8 o

7、f 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.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),f

8、alse); for i:=1 to n do begin readln(s); for j:=1 to n do cani,j:=sj=-; end; end;17阳山书屋procedure bfs;/广度优先搜索 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; /记录出队

9、结点状态 for k:=1 to 8 do /扩张结点：走下一步 begin xx:=x+dxk; yy:=y+dyk; if canxx,yy and (distxx,yy=-1) then /能走但没走过 begin distxx,yy:=distx,y+1; inc(tail); qtail,1:=xx; qtail,2:=yy; end; end; end; end;18阳山书屋 设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可

10、通过，要另找路径。输入例子：（从文件中读取数据） 80 0 0 1 1 0 1 01 0 1 1 0 1 1 00 1 0 0 1 0 0 10 0 1 1 0 1 0 10 1 0 0 0 1 1 00 1 1 1 1 1 0 10 0 1 1 1 0 1 11 1 0 0 0 0 0 0入口：（1，1）；出口：（1，8）输出要求：找出一条 从入口（左上角）到出口（又上角）的最短路径。 8(1 1)(2 2)(3 3)(3 4)(4 5)(3 6)(3 7)(2 8)(1 8)2、迷宫问题19阳山书屋Bfs算法：1）先求最少步数const fin=migong.in; fout=migong

11、.out; maxn=100; dx:array1.8of integer=(0,1,1,1,0,-1,-1,-1); dy:array1.8of integer=(-1,-1,0,1,1,1,0,-1);type node=record row,col:integer; /记录行与列 depth:integer; /离起点的距离 end;var can:array0.maxn+1,0.maxn+1 of boolean; q:array1.maxn*maxn of node; n,head,tail:integer;20阳山书屋 head:=0; tail:=1; q1.row:=1; q1

12、.col:=1; q1.depth:=0; can1,1:=false; while headtail do begin inc(head); x:=qhead.row; y:=qhead.col; step:=qhead.depth; for k:=1 to 8 do begin xx:=x+dxk; yy:=y+dyk; if canxx,yy then /没走过，没入过队 begin if (xx=1)and(yy=n) then print(step+1); inc(tail); qtail.row:=xx; qtail.col:=yy; qtail.depth:=step+1; ca

13、nxx,yy:=false; end; end; end; print(-1);/无解的情况21阳山书屋 procedure print(ans:integer); var j:integer; begin assign(output,fout); rewrite(output); if ans=-1 then writeln(no answer) else writeln(ans); close(output); halt; end;22阳山书屋1和2是怎样保证不重复进队列的？重复进队列，做了无用功，浪费空间和时间。设置合适的布尔数组23阳山书屋 给定10个盒子排成一行，其中有两个相邻的盒子

14、是空的，其余的盒子中有4个A和4个B。 移动规则：任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持不变。 目标：全部的A在左边，全部的B在右边，空格在中间。 对于任意给定的一个排列顺序，最少经过多少次移动，能达到目标序列。输入：一行：初始序列，空格用0代替。输出：初始序列达到目标的最少移动次数。样例：输入：输出：5AAAABBBBABBAABAB3、中国盒子问题 （box） 初始：目标：24阳山书屋ABAB00ABABA00BBAABABAAABB00BABAAA00BBBABAAAABBBB00AAAA00BBBB1234525阳山书屋1)、问题：初始序列达到目标的最少移动次数。

15、适合使用bfs算法。 2)、队列需要保存的状态： 转化后的字符串s; 转换需要的步数depth。 适合用记录数据类型： type node=record str:string; depth:integer; end;3)、状态的多少（队列的大小）：9!/(4!*4!)=63026阳山书屋4)、状态的转移：看两个空格的能移动的位置 任意两相邻字母可移到空盒子中去，但这两个字母的原来顺序保持改变 ABBAABAB1）、确定空格的位置： sp:=pos(0,s);spS=i （1-9）2）、i，i+1与sp，sp+1位置的字符交换：条件：( i+1 sp ) or ( sp+1i ) /前后情况3）

16、、交换：Tem=stemsp:=si; temsp+1:=si+1; temi:=0; temi+1:=0;？27阳山书屋5)、判重：是否已进过队列 从队中的所有状态查找：1.tail function find(tem:string):boolean; var j:integer; begin for j:=1 to tail do if tem=qj.str then exit(true); exit(false); end;28阳山书屋 head:=0; tail:=1; q1.str:=s1; q1.depth:=0; while headtail do begin inc(head)

17、; s:=qhead.str; step:=qhead.depth; sp:=pos(0,s); for i:=1 to 9 do begin tem:=s; if (i+1sp)or(sp+1i) then begin temsp:=si; temsp+1:=si+1; temi:=0; temi+1:=0; if tem=st then print(step+1); if not find(tem) then begin inc(tail); qtail.str:=tem; qtail.depth:=step+1; end; end; end; end;29阳山书屋广度优先 搜索算法（bf

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

19、 /按规则扩展下一层新的子结点 if 条件满足 then Begin 生成新的结点; if 新结点队列中没出现过 then 保存新结点（入队列）； if 新结点是目标结点 then print(tail) 搜索结束； End End；Print(-1); /无解BFS的基本框架：31阳山书屋type queue=record 必要的有用的状态; father:longint;/父亲结点，输出路径 depth:longint; end;q:array1.maxn of queue;队列的大小作为全局变量，避免用作局部变量，尤其当maxn很多时。32阳山书屋/输出转化过程：路线 procedure

20、 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;33阳山书屋常用的判重方法：合适的布尔类型 (迷宫类)朴素的队列查找 find(1.tail)：如果多，时间长构造合适的哈希函数：为了分类，减少查找时间影响bfs时间的关键：重点减少不必要的扩展结点34阳山书屋【问题描述】对于只含有字母A和B的字符串，给定初始串s1和目标串s2。同时

21、给定串中字母的移动规则：每次移动只能交换两个相邻的字母。任务：求s1最少经过多少次交换得到s2。【输入】第一行：初始串s1。第二行：目标串s2。【输出】由s1生成s2的最少交换次数。【数据范围限制】100%的数据：s1和s2长度=20。【输入输出样例】 change.inchange.outAABBAABAAAAB44、A B交换35阳山书屋保存的状态状态数量：队列的大小状态的扩展条件判重方法分析：36阳山书屋判重的改进： 构造哈希函数：把AB串对应于二进制A:0 B:1AB串和二进制一一对应关系。AABBAA00110012。f12=true大小：20位：22037阳山书屋function

22、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)=true38阳山书屋 head:=0; tail:=1; q1.str:=s1; q1.depth:=0; fhash(s1):=true; while headtail do begin inc(head); s:=qhead.str; step:=qhead.depth; for i:=1 to n-1 do if sisi+1 then

23、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;39阳山书屋 有两个无刻度标志的水杯，分别可装x升和y升的水。设另一个水缸，可以用来向水杯灌水或从水杯向水缸里倒水，两个水杯之间也可以相互倒水。已知x升的水杯开始是盛满水的，y升的杯子是空的，问如何通过倒水和灌水操作，用最少的步数能在y升的杯子里量出z升水。5：倒

24、水问题CA水缸（足够的水,未满）X=20 Y=15 Z=10Y=10？B40阳山书屋输入： 一行：x，y，z（0)and(by)。结果： 要么A空（ay-b）。 可以从A中倒mina,y-b升水给B。状态： A：a-mina,y-b; B：b+mina,y-b。43阳山书屋2: ACxax-ayby-bBAC条件： A中有水：a0结果： 把A中水全倒入C状态： A: 0; B:b不变。44阳山书屋3: BAxax-ayby-bBAC条件：B中有水且A不满，即 (b0)and(ax)。结果: 要么B空（bx-a）。 可以从B中倒minb,a-x升水给A。状态：A：a+minb,x-a; B：b-

25、minb,x-a。45阳山书屋4: BCxax-ayby-bBAC条件： B中有水：b0结果: 把B中水全倒入C状态： A: a ;B:0升。46阳山书屋5: CAxax-ayby-bBAC条件： A不满: ax。结果: 把A倒满状态： A: x满，B：b不变。47阳山书屋6: CBxax-ayby-bBAC条件： B不满：by。结果: 把B倒满状态： A：a不变，B：y满。48阳山书屋算法实现：每倒一次需要保存的状态：a,b,father,depth倒完一次后检查：a和b的值：出现 ? b=z ?队列的大小：max=100；（max+1）*（max+1）怎样判断重复： fi,j:boolean。A中出现i升，B中出现j升水的情况；49阳山书屋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 boo