题目地址：https://www.luogu.org/problemnew/show/P1032
洛谷训练场BFS的训练题呀。
“BFS不就是用队列的思想去遍历一切情况嘛。我已经不是小孩子了，我肯定能做出来！”
A FEW MINUTES LATER
“QAQ我错了，这题怎么用BFS的思想呀。”
毫无头绪的我选择向题解求助。
/学习从来就不是一件容易的事情，但这可以做成一件让自己快乐的事情/
耐下心来，仔细阅读以及翻资料，终于看明白了ShawnZhou大牛的代码（以下粘贴的代码均是ShawnZhou大牛的代码，侵删）。
尝试总结一下知识点：
BFS、queue、map、以及字符串（string）的处理
题目有必定的两个字符串的输入——最初形态＆最终形态；
然后下面就是状态的一一对应：x1 -> y1； x2 -> y2； ......
于是大牛这么构造这情况：
string a, b; // 最初形态＆最终形态
string orginal[maxn];
string translated[maxn];
int n; // n = 0
//...
cin >> a >> b; // 输入把我看呆了，又学到了新姿势
while(cin >> orginal[n] >> translated[n]) n++;
BFS:
运用队列，这里遍历的情况是变化后的字符串与其所在的第i步后两种记录，所以大牛用到了pair的思想（只不过他这里用结构体，给我这小白真的太友好了）
这里map的剪枝个人觉得也是给我上了一门课——剪枝真的好神奇！map这STL tql！（map的详细介绍：http://www.cplusplus.com/reference/map/map/?kw=map）
结果，貌似真的如果大牛所说：一个平淡无奇的bfs过程
struct node{
string str;
int step;
};
void bfs(){
queue<node> q;
node s;
s.str = a;
q.push(s);
while(!q.empty()){
node u = q.front();
q.pop();
string temp;
if(ma.count(u.str) == 1) // 剪枝，判断重复的路径
continue;
if(u.str == b){
ans = u,step;
break;
}
ma[u.str] = 1;
for(int i = 0; i < u.str.length(); i++) // 枚举当前串所有可能位置
for(int j = 0; j < n; j++) { // 枚举所有可能手段
temp = trans(u.str, i, j); // 这个 trans() 是处理字符串的函数
if(temp != ""){
node v;
v.str = temp;
v.step = u.step + 1;
q.push(v);
}
}
}
}
trans()函数：
学到了新的知识 string 的 substr()；（substr()详解：http://www.cplusplus.com/reference/string/string/substr/)
效果是判断该字符串是否满足条件变换，如果满足，则进行变换并把变换效果传进队列（bfs下面的if语句条件的方法体）
如果条件的长度比此时目标字符串的长度要长，无疑是不可能达成条件的，直接返回（第一个return）
然后逐一从字符串的目标那里开始与条件字符串的“0”位开始比较（bfs()第一个for语句就有逐一遍历原字符串的每个字符的效果——这个“原字符串”是指队列里每个元素的str），如果不满足每一个字符都相同则返回第二个return（效果跟第一个return一样）
最后进行的是对原字符串的转换（详细过程请读者大牛手动模拟一下吧，小白也说不清楚QUQ,dbq)。
string trans(const string &str,int i,int j){//借鉴了stdcall大爷的思想
string ans = "";
if (i+orginal[j].length() > str.length())
return ans;
for (int k=0; k < orginal[j].length();k++)
if (str[i+k] != orginal[j][k])
return ans;
ans = str.substr(0,i);
ans+=translated[j];
ans+=str.substr(i+orginal[j].length());
return ans;
}
最后贴一下完整的代码：ShawnZhou大牛的代码（喜欢的前往本题的题解为大牛点赞打call呀）
https://www.luogu.org/problemnew/solution/P1032
ShawnZhou小白是某二本财经大学的科班学生，入坑时间晚，还是有很多东西要虚心向大牛们学习。
以后请多多指教/