百度为什么不收录网站的某个版块,浙江新地标建设集团网站,国外网站推广软件,南京已经开始二次感染了190. 字串变换 - AcWing题库
已知有两个字串 A, B 及一组字串变换的规则#xff08;至多 66 个规则#xff09;:
A1→B1
A2→B2
…
规则的含义为#xff1a;在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。
例如#xff1a;A#xff1d;abcd B#xff1d;xy…190. 字串变换 - AcWing题库
已知有两个字串 A, B 及一组字串变换的规则至多 66 个规则:
A1→B1
A2→B2
…
规则的含义为在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。
例如Aabcd Bxyz
变换规则为
abc →→ xu ud →→ y y →→ yz
则此时A 可以经过一系列的变换变为 B其变换的过程为
abcd →→ xud →→ xy →→ xyz
共进行了三次变换使得 A 变换为 B。
注意一次变换只能变换一个子串例如 Aaa Bbb
变换规则为
a →→ b
此时不能将两个 a 在一步中全部转换为 b而应当分两步完成。
输入格式
输入格式如下
A B A1 B1 A2 B2 …
第一行是两个给定的字符串 A 和 B。
接下来若干行每行描述一组字串变换的规则。
所有字符串长度的上限为 20。
输出格式
若在 10 步包含 10 步以内能将 A 变换为 B 则输出最少的变换步数否则输出 NO ANSWER!。
输入样例
abcd xyz
abc xu
ud y
y yz输出样例
3
解析
双向BFS比单项BFS要快得多为什么呢假设每一种状态能扩展出是个状态那么单项扩展十步就是10^10状态,而如果是双向BFS其中一段从结果开始那么两端一共扩展得出的状态是2*10^5
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;
const int N 8;
int n;
string A, B;
string a[N], b[N];int extend(queuestring q, unordered_mapstring, int da, unordered_mapstring, int db, string a[N], string b[N]) {int t da[q.front()];while (q.size() da[q.front()] t) {auto tt q.front();q.pop();for (int i 0; i n; i) {for (int j 0; j tt.size(); j) {if (tt.substr(j, a[i].size()) a[i]) {string state tt.substr(0, j) b[i] tt.substr(j a[i].size());if (db.count(state))return da[tt] db[state] 1;if (da.count(state))continue;da[state] da[tt] 1;q.push(state);}}}}return 11;
}int bfs() {if (A B)return 0;queuestringqa, qb;unordered_mapstring, intda, db;qa.push(A);qb.push(B);da[A] 0;db[B] 0;int step 0;while (qa.size() qb.size()) {int t;if (qa.size() qb.size()) textend(qa, da, db, a, b);else textend(qb, db, da, b, a);if (t 10)return t;if (step 10)return 11;}return 11;
}int main() {cin A B;while (cin a[n] b[n])n;int ret bfs();if (ret 10)printf(%d\n, ret);else printf(NO ANSWER!\n);return 0;
}
