双向BFS总结

· · 题解

================================================================

===========================开始分割线============================

================================================================

这道题很明显是一道 B F S 的 模 板 题

但是···············

这道题更加明显的是一道 [ 双 向 B F S 模 板 题 ]

因为
这道题同时给出了初始状态和目标状态
所以
用双向BFS可以使得运行速度大大提升

================================================================

========================真正的开始分割线=========================

================================================================

画个图来举栗子！

我们假设上面的S点是初始状态，下面的T点是目标状态，那么单向的BFS会形成这么一个树状图形，每一次扩展都相当于是树枝的延伸，最后如果延伸到了T那么就结束了。

但是我们很明显的可以发现有很多冗余的BFS搜索枝是没有意义的，它们过于偏离了T的方向！

我们同时可以发现，其实我们也可以从T开始搜索，造出一个上大下小的BFS搜索树，同样可以起到BFS的作用，当搜索到S点的时候就结束了！

而这样做的时候同样也有很多的冗余搜索枝。

这个时候我们考虑双向BFS！！如果我们同时从上面和下面开始延伸这两棵树子的话，一旦两头撞在一起就可以说明搜索到了，因为两颗搜索树的搜索规则是相反的，两棵树相遇的时候从一边的节点一定可以顺着另外一边的搜索枝到达终点！

这样一来我们就可以去除很多搜索枝，用几何关系不难证明至少会减少百分之五十的搜索空间与时间，但是实际上每一次搜索带来的横向扩张远远不止+1，有的时候可以翻倍或者更多，所以这棵树子的图形往往是一个指数函数图像为边界的搜索树，深度每每+1，就会带来大量的新搜索节点，而双向BFS可以减少大量的搜索节点。

对于这道题，我们可以通过map去实现查找现在我们所搜索到的节点是否出现过（如果是同一边的搜索树里面的，那么就不用再把这个节点入队了，假如是对面的，那么就意味着两棵搜索树碰面了！算法结束！）

而每次出队的时候，只能够出上一层的搜索节点，不可以使用这一层的搜索节点，保证两边一步一步地走，所以map里面所对应的int是这个搜索节点对应的层数-1（具体细节可以模拟）

[15ms] AC code

#include<bits/stdc++.h>
using namespace std;
string a[10],b[10],s,t;
int n=1;
map <string,int> A,B;//pair< string , step + 1 >
queue <string> A_,B_; 
inline void initialization()
{
    cin>>s>>t;
    while(cin>>a[n]>>b[n])n++;
}
inline int bfs()
{
    int step=0;
    A_.push(s);//开始状态
    A[s]=0;//开始状态的层数 
    B_.push(t);//开始状态
    B[t]=0;//结束状态的层数 
    string s,s2;
    while(++step<=5)//一边是10步之内，那么两边一起走就是5步之内 
    {
        while(A[A_.front()]==step-1)//保证是上一层的 
        {
            s=A_.front();
            A_.pop();
            for(int i=1;i<=n;i++)//对于每一个转换方案遍历 
            {
                unsigned int pos=0;//遍历开始搜索的节点，结合string::find( key_string , starting ) 
                while(pos<s.length())
                {
                    if(s.find(a[i],pos)==s.npos)break;//如果找不到了 
                    s2=s;
                    s2.replace(s2.find(a[i],pos),a[i].length(),b[i]);//replace( starting , length , substitution )
                    if(A.find(s2)!=A.end())//这棵树里面之前出现过 
                    {
                        pos++;
                        continue;
                    }
                    if(B.find(s2)!=B.end())return step*2-1;//对面的搜索树里面出现过，由于是上面先走，所以-1 
                    A_.push(s2);//入队 
                    A[s2]=step;
                    pos++;
                }
            }
        }
        while(B[B_.front()]==step-1)//保证是上一层的 
        {
            s=B_.front();
            B_.pop();
            for(int i=1;i<=n;i++)//对于每一个转换方案遍历 
            {
                unsigned int pos=0;//遍历开始搜索的节点，结合string::find( key_string , starting ) 
                while(pos<s.length())
                {
                    if(s.find(b[i],pos)==s.npos)break;//如果找不到了 
                    s2=s;
                    s2.replace(s2.find(b[i],pos),b[i].length(),a[i]);//replace( starting , length , substitution )
                    if(B.find(s2)!=B.end())//这棵树里面之前出现过 
                    {
                        pos++;
                        continue;
                    }
                    if(A.find(s2)!=A.end())return step*2;//对面的搜索树里面出现过，由于是上面先走，所以-1 
                    B_.push(s2);//入队 
                    B[s2]=step;
                    pos++;
                }
            }
        }
    }
    return -1;
}
int main()
{
    initialization();
    int ans=bfs();
    if(ans==-1)
    printf("NO ANSWER!");
    else printf("%d",ans);
    return 0;
}

================================================================

===========================结束分割线============================

================================================================

Thx for watching the patience!