双向广度优先搜索算法
广度双向搜索的概念
所谓双向搜索指的是搜索沿两个力向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。
广度双向搜索算法
广度双向搜索通常有两种方法：
1. 两个方向交替扩展
2. 选择结点个数较少的那个力向先扩展．方法2克服了两方向结点的生成速度不平衡的状态，明显提高了效率。
算法说明：
设置两个队列c:array[0..1,1..maxn] of jid，分别表示正向和逆向的扩展队列。
设置两个头指针head:array[0..1] of integer 分别表示正向和逆向当前将扩展结点的头指针。
设置两个尾指针tail:array[0..1] of integer 分别表示正向和逆向的尾指针。
maxn表示队列最大长度。
双向宽搜的应用：
{
题目来源：NOIP2002提高组试题
描述 Description
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
A1$ -> B1$
A2$ -> B2$
规则的含义为：在 A＄中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
例如：A$＝'abcd'B$＝'xyz'
变换规则为：
‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
‘abcd’->‘xud’->‘xy’->‘xyz’
共进行了三次变换，使得 A$ 变换为B$。
输入格式 Input Format
A$ B$
A1$ B1$
A2$ B2$ |-> 变换规则
... ... /
所有字符串长度的上限为 20。
输出格式 Output Format
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；
否则输出"NO ANSWER!"
样例输入：
abcd xyz
abc xu
ud y
y yz
样例输出：
3
题目类型：双向广搜
分析：很经典的搜索，双向进行，一种从初始状态向目标状态搜索，另一种从目标状态向初始状态搜索，哪一种的该层节点少就从哪一层向上 或向下搜索，直到两种搜索相交，0ms暴爽，详细解释看下面
}
program NOIP2002p2;
type pp=record
d:longint;
s:string;
end;
var head,tail:array[1..2] of longint;
q:array[1..1000,1..2] of pp;
st:string;
a:array[1..10,1..2] of string;
i,j,tot,k:longint;
//init--------------------------
procedure init;//a[tot,1]记录第tot－1个变换规则的A$字串，a[tot,2]记录第tot－1个变换规则的B$字串，因为第一个是起始串和终止串
var x:longint;
s:string;
begin
tot:=0;
while not eof do
begin
inc(tot);
readln(s);
x:=pos(' ',s);
a[tot,1]:=copy(s,1,x-1);
a[tot,2]:=copy(s,x+1,length(s)-x);
end;
end;
//prepare-----------------------
procedure prepare;//准备工作：第一个队列的头指针指向第一个A$串，第二个队列的头指针指向第一个B$串，存储变换次数的记录均赋值为0
var i,j,k:longint;
begin
head[1]:=1; tail[1]:=1;
head[2]:=1; tail[2]:=1;
q[head[1],1].s:=a[1,1]; q[head[1],1].d:=0;
q[head[2],2].s:=a[1,2]; q[head[2],2].d:=0;
end;
//check-------------------------
procedure check(s1:string; t:longint);
var i:longint;
f:boolean;
begin
f:=false;
for i:=1 to tail[t]-1 do if q[i,t].s=s1 then f:=true;//检验前面的队列中是否出现过相同的字符串
if f=true then dec(tail[t])//出现过，删除掉扩展的节点
else//没出现过的话，向另一个队列中寻找是否有重合，有，即找到了目标，对头成功，大功告成^-^,结束程序即可；没有，接着搜呗！
begin
for i:=1 to tail[3-t] do
if q[i,3-t].s=s1 then
begin
writeln(q[tail[t],t].d+q[i,3-t].d);
close(input); close(output);
halt;
end;
end;
end;
//wide--------------------------
procedure wide(x:longint);
var s1:string;
i,j,t:longint;
begin
for i:=2 to tot do//从第二个变换规则开始枚举A$或B$串
begin
t:=pos(a[i,x],q[head[x],x].s);//从父亲节点的字符串中寻找可以变换的位置
if t<>0 then//找到后扩展节点
begin
repeat
inc(tail[x]);
q[tail[x],x].s:=q[head[x],x].s;
delete(q[tail[x],x].s,t,length(a[i,x]));//删除掉需要更换的字符串
insert(a[i,3-x],q[tail[x],x].s,t);//插入变换后的字符串，当前串即为更新后的字符串
q[tail[x],x].d:=q[head[x],x].d+1;//变换次数加一
check(q[tail[x],x].s,x);//检验是否出现过相同的状态
t:=t+pos(a[i,x],copy(q[head[x],x].s,t+1,length(q[head[x],x].s)-t)); {一个字符串中可能有多个可交s换串}
until pos(a[i,x],copy(q[head[x],x].s,t+1,length(q[head[x],x].s)-t))=0
end;
end;
inc(head[x]);
end;
//work--------------------------
procedure work;
begin
repeat
if (head[1]<=tail[1])and(q[tail[1],1].d<=10)and(tail[1]<=tail[2]) then wide(1);
if (head[2]<=tail[2])and(q[tail[2],2].d<=10)and(tail[1]>tail[2]) then wide(2);//尽量做到两个队列在数量上保持一致
until (head[1]>tail[1]) or (head[2]>tail[2]) or (q[tail[1],1].d+q[tail[2],2].d>10);//中止条件
end;
//main--------------------------
begin
init;
prepare;
work;
writeln('NO ANSWER!');
end.