题目描述
已知有两个字串 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 xyzabc xuud yy yz
输出样例
3
差不多是一道水题吧。。就是 bfs 暴搜就行。只不过在搜的时候要注意以下几点：
1.每一次是如何变换的
1 string change(const string& now, int st, int num) //now字符串第st位，第num条变换规则 2 { 3 for(int i = 0; i < a1[num].length(); ++i) 4 { 5 if(st + i >= now.length()) return ""; //若超出原字符串长度或 6 if(now[st + i] != a1[num][i]) return ""; //有一位不符合规则，就不能变换，返回空字符串 7 } 8 string ret; 9 //变换分三步 10 for(int i = 0; i < st; ++i) ret += now[i];//1.将原字符串不用变换的前半部分复制下来 11 ret += b1[num]; //2.再加上变换部分 12 for(int i = st + a1[num].length(); i < now.length(); ++i) ret += now[i];//3.加上原字符串剩下部分 13 return ret;14 } 用 string 的好处是，它支持加减运算，就是增加或减去某一字符串，而不用库里的 strcpy 函数。
2.再用bfs时，要记录之前的状态，防止又退回去，进入死循环。但这道题开 vis 数组就不太合适，因为每一个状态是一个字符串。所以最好开一个 map 来记录状态，并判重。
3.若按 2 的方法，因为是字符串的操作，大数据可能会超时，所以可以将字符串编码为 unsigned long long，一个简单的hash
1 ull hash(const string& now){2 ull ret = 0;3 for (int i = 0; i < now.length(); i++){4 ret += now[i] - 'a' + 1; ret *= 27;5 }6 return ret;7 } 完整代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include
值得一提的是，这里的 map 发挥了两个作用，一个是 vis 数组，另一个是相当于记录步数的 dis数组
