南城网站建设公司企业大学网站建设计划

题目描述:
大魔术师PIPI有N个转换魔咒，每个转换魔咒可以将一个字符串变成另一个字符串。
比如说：
“PIPI”->“POPO”
“boy”->“girl”
“boy”->“u”
“isau”->“OJ”
那么对于字符串"PIPIisaboy"，大魔术师PIPI可以通过2次魔咒将"PIPIisaboy"变成"POPOisagirl"。
也可以通过2次魔咒将"PIPIisaboy"变成"PIPIOJ"。
现在你知道了PIPI的所有魔咒，想让他把字符串A变成字符串B，请输出变换所需的最少步数。
输入：
输入包含单组测试样例。
第一行输入字符串A和字符串B。1≤|A|，|B|≤30。
接下来输入一个数字N，代表转换魔咒的个数(1≤N≤10)。
接下来N行，每一行输入一个转换规则 X Y，代表可以将字符串X转化为Y。 1≤|X|，|Y|≤30。
本题给出的所有字符串均不包含空格。
输出：
如果在10次之内能将A变为B，输出从字符串A变为字符串B的最少次数。否则输出-1。
样例输入：
PIPIisaboy POPOisagirl
4
PIPI POPO
boy girl
boy u
isau OJ
样例输出：
2

题解代码如下：

#include <bits/stdc++.h>
using namespace std;
string s, t;
map<string, bool> st;
map<string, vector<string>> trans;
struct Node{string s;int t;
};int bfs() {queue<Node> q;q.push({s, 0});st[s] = true;while (q.size()) {auto now = q.front(); q.pop();if (now.t > 10) continue;if (now.s == t) {return now.t;}for (int L = 0; L < now.s.size(); L++) {for (int len = 1; L + len - 1 < now.s.size(); len++) {string subs = now.s.substr(L, len);if (trans.count(subs)) {for (int i = 0; i < trans[subs].size(); i++) {string ns = now.s;ns.replace(L, len, trans[subs][i]);if (!st[ns]) {st[ns] = true;q.push({ns, now.t + 1});}}}}}}return -1;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> s >> t;int n;cin >> n;while (n--) {string a, b;cin >> a >> b;trans[a].push_back(b);}cout << bfs() << endl;return 0;
}