题意：给起始和终止串A和B，以及不超过6个字符串变换规则，求A->B能否在10步以内变换完成。
分析：暴力bfs每次有6条路可以走，时间复杂度是6^10 大概6e8的时间复杂度，会TLE。于是这题是一道经典的双向bfs。 直接开两个队列，两个map，暴力搜1~5步即可。
双向bfs的时间复杂度是2 * (6 ^ 5) = 1e4级别。所以双向bfs在指数级增长的搜索中优势巨大。
'
void solve(){
string a, b;
cin >> a >> b;
vector<pair<string, string>> rules(1);
//int t = 1;
while (cin >> rules[0].first >> rules[0].second){
rules.emplace_back(rules[0]);
// t ++;if (t > 3) break;
}
int rule_size = int(rules.size()) - 1;
map<string, bool> go;
map<string, bool> come;
queue<pair<string, int>> qs, qe;
qs.emplace(a, 0);
qe.emplace(b, 0);
go[a] = true;
come[b] = true;
auto bfs = [&]()->int{
while (!qe.empty() || !qs.empty()){
int now = qs.front().second;
if (now >= 5){
break;
}
while (!qs.empty() && qs.front().second == now){
auto[s, cur] = qs.front();
qs.pop();
for (int i = 1; i <= rule_size; ++i){
for (int j = 0; j < int(s.size()); ++j){
if (s.find(rules[i].first, j) == s.npos){
break;
}
auto tmp_s = s;
tmp_s.replace(tmp_s.find(rules[i].first, j), int(rules[i].first.size()), rules[i].second);
if (!go.count(tmp_s)){
if (come.count(tmp_s)){
return (now + 1) * 2 - 1;
}
qs.emplace(tmp_s, now + 1);
go[tmp_s] = true;
}
}
}
}
now = qe.front().second;
if (now > 5){
break;
}
while (!qe.empty() && qe.front().second == now){
auto[s, cur] = qe.front();
qe.pop();
for (int i = 1; i <= rule_size; ++i){
for (int j = 0; j < int(s.size()); ++j){
if (s.find(rules[i].second, j) == s.npos){
break;
}
auto tmp_s = s;
tmp_s.replace(tmp_s.find(rules[i].second, j), int(rules[i].second.size()), rules[i].first);
if (!come.count(tmp_s)){
if (go.count(tmp_s)){
return (now + 1) * 2;
}
come[tmp_s] = true;
qe.emplace(tmp_s, now + 1);
}
}
}
}
}
return -1;
};
int ans = bfs();
if (ans == -1){
cout << "NO ANSWER!" << '\n';
}
else{
cout << ans << '\n';
}
}
'