算法提高之字串变换

• 核心思想：双向广搜

  • 双向bfs 建立两个队列 一起bfs到中间态
  • 

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <unordered_map>
    
    using namespace std;
    const int N = 6;
    
    int n;
    string A,B;
    string a[N],b[N];
    
    int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db, 
        string a[N], string b[N])
    {
        int d = da[q.front()];  //确定当前层数
        while(q.size() && da[q.front()] == d)  //如果是同一层的就搜
        {
            auto t = q.front();
            q.pop();
             
            for(int i=0;i<n;i++)  //遍历所有规则
            {
                for(int j=0;j<t.size();j++)
                {
                    if(t.substr(j,a[i].size()) == a[i])  //有相应的子串
                    {
                        //构造新的字符串
                        string r = t.substr(0,j) + b[i] + t.substr(j+a[i].size());
                        if(db.count(r)) return da[t] + db[r] + 1;  //如果b中已经搜到过
                        if(da.count(r)) continue;
                        da[r] = da[t] + 1;
                        q.push(r);
                    }
                }
            }
        }
        return 11;
    }
    int bfs()
    {
        if(A == B) return 0;
        queue<string> qa,qb;
        unordered_map<string,int> da,db;
        
        qa.push(A), qb.push(B);
        da[A] = db[B] = 0;
        int step = 0;  //记录步数 如果超过10 直接return -1
        while(qa.size() && qb.size())
        {
            int t;
            //优先扩展长度短的那个
            if(qa.size()<qb.size()) t = extend(qa,da,db,a,b);  //注意规则是a->b
            else t = extend(qb,db,da,b,a);  //规则是b->a 反向
            
            if(t <= 10) return t;  //没找到之前会返回一个>10的数
            if(++ step == 10) return -1;
        }
        return -1;
    }
    int main()
    {
        cin>>A>>B;
        while(cin>>a[n]>>b[n]) n++;
        
        int t = bfs();
        if (t == -1) puts("NO ANSWER!");
        else cout << t << endl;
    
    }