ACWING 190. 字串变换（双向bfs）

本文主要是介绍ACWING 190. 字串变换（双向bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路： 膜着yxc dalao的代码写的。没想到是双向bfs。
也就是说，对于字符串A,B。A->B的过程来一次bfs，B->A的过程来一次bfs，两次bfs的结果综合起来，相加就是结果。

1 中间相加结果大于10就退出
2 每次取队顶（也就是变换值最小的次数）的较小的那一半，进行处理。
3 初始化da[A] = 0, db[B] = 0，中间到了队顶的字符串，枚举每一位可以进行什么样的交换。然后用map记录对应字符串的交换值相加就是结果（注意当前对应哪个字符串）。

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>using namespace std;int n;
string aa[10],bb[10];int solve(queue<string> &q,map<string,int> &da,map<string,int> &db,string a[],string b[])
{string t = q.front();q.pop();for(int i = 0;i < t.size();i++){for(int j = 1;j <= n;j++){if(t.substr(i,a[j].size()) != a[j])continue;string r = t.substr(0,i) + b[j] + t.substr(i + a[j].size());if(db.count(r))return db[r] + da[t] + 1;if(da.count(r))continue;da[r] = da[t] + 1;q.push(r);}}return -1;
}int bfs(string x,string y)
{queue<string>qa,qb;map<string,int>da,db;qa.push(x);da[x] = 0;qb.push(y);db[y] = 0;while(qa.size() && qb.size()){if(da[qa.front()] + db[qb.front()] > 10)return 11;int res;if(da[qa.front()] < db[qb.front()])res = solve(qa,da,db,aa,bb);else res = solve(qb,db,da,bb,aa);if(res != -1)return res;}return 11;
}int main()
{string A,B;cin >> A >> B;n = 1;while(cin >> aa[n] >> bb[n])n++;n--;int ans = bfs(A,B);if(ans <= 10)printf("%d\n",ans);else printf("NO ANSWER!\n");return 0;
}