题目描述

已知有两个字串 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。

输入格式
输入格式如下：

A B
A1 B1 \
A2 B2 |-> 变换规则
… … /

所有字符串长度的上限为 20。

输出格式
若在 10 步（包含 10步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出”NO ANSWER!”

输入样例：
abcd xyz
abc xu
ud y
y yz
输出样例：
3

采用双向广搜来解题 时间复杂度O(2 * n ^ 5)

从起点和终点进行双向广搜，注意细节应该没什么大问题~。~

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 25;

string s,e;

int n;

string a[N],b[N];

unordered_map<string,int> da,db;

int extend(queue<string> &q,string a[],string b[],unordered_map<string,int> &da,unordered_map<string,int> &db)
{
    string t = q.front();
    q.pop();
    for(int i=0;i<n;i++)
        for(int l=0;l+a[i].size()<=t.size();l++)
            if(t.substr(l,a[i].size())==a[i])
            {
              string str = t.substr(0,l) + b[i] + t.substr(l + a[i].size()); 
              if(db.count(str)) return db[str] + da[t] + 1;
              if(!da.count(str))
              {
                  da[str] = da[t] + 1;
                  q.push(str);
              }
            }
    return -1;
}

int bfs(){

    queue<string> qa;
    queue<string> qb;

    qa.push(s);
    da[s] = 0; 
    qb.push(e);
    db[e] = 0;

    while(qa.size() && qb.size())
    {
        if(da[qa.front()] + db[qb.front()] >=10) return 11;//根据BFS的性质，队首是最小的距离，如果超过10就无解了

        int t;

        //选择分支较小的点延展来进行优化。
        if(qa.size() <= qb.size()) t = extend(qa,a,b,da,db);
        else t = extend(qb,b,a,db,da);

        if(t!=-1)
            return t;
    }

    return 11;
}

int main(){

    cin >> s >> e;

    if(s==e)
    {
        puts("0");
        return 0;
    }

    while(cin >> a[n] >> b[n]) n++;

    int res = bfs();

    if(res > 10) puts("NO ANSWER!");
    else cout << res << endl;


    return 0;
}