You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
85 lines
2.1 KiB
85 lines
2.1 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int INF = 0x3f3f3f3f;
|
|
const int N = 10;
|
|
string A, B; //原始串
|
|
string a[N], b[N]; //规则
|
|
queue<string> qa, qb; //双端队列
|
|
unordered_map<string, int> da, db; //此字符串，是几步转移过来的
|
|
int n;
|
|
int ans = INF;
|
|
|
|
inline bool expandA() {
|
|
string u = qa.front();
|
|
qa.pop();
|
|
if (db.count(u)) {
|
|
ans = da[u] + db[u];
|
|
return true;
|
|
}
|
|
for (int i = 0; i < u.size(); i++) //枚举字符串的每一位
|
|
for (int j = 0; j < n; j++) { //枚举规则
|
|
if (u.substr(i, a[j].size()) == a[j]) {
|
|
string ts = u.substr(0, i) + b[j] + u.substr(i + a[j].size());
|
|
if (!da.count(ts)) {
|
|
qa.push(ts);
|
|
da[ts] = da[u] + 1;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
inline bool expandB() {
|
|
string u = qb.front();
|
|
qb.pop();
|
|
if (da.count(u)) {
|
|
ans = da[u] + db[u];
|
|
return true;
|
|
}
|
|
for (int i = 0; i < u.size(); i++)
|
|
for (int j = 0; j < n; j++) {
|
|
if (u.substr(i, b[j].size()) == b[j]) {
|
|
string ts = u.substr(0, i) + a[j] + u.substr(i + b[j].size());
|
|
if (!db.count(ts)) {
|
|
qb.push(ts);
|
|
db[ts] = db[u] + 1;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
void bfs() {
|
|
//两个串分别入队列
|
|
qa.push(A), qb.push(B);
|
|
da[A] = 0, db[B] = 0;
|
|
|
|
//双向广搜套路
|
|
while (qa.size() && qb.size()) {
|
|
if (qa.size() < qb.size()) {
|
|
if (expandA()) return;
|
|
if (expandB()) return;
|
|
} else {
|
|
if (expandB()) return;
|
|
if (expandA()) return;
|
|
}
|
|
}
|
|
}
|
|
|
|
//可以AC掉本题,双向广搜+大小队列对比优化
|
|
// 17ms
|
|
int main() {
|
|
//加快读入
|
|
cin.tie(0), ios::sync_with_stdio(false);
|
|
|
|
cin >> A >> B;
|
|
while (cin >> a[n] >> b[n]) n++;
|
|
|
|
bfs();
|
|
|
|
if (ans > 10)
|
|
puts("NO ANSWER!");
|
|
else
|
|
printf("%d\n", ans);
|
|
return 0;
|
|
} |