|
|
## [$AcWing$ $190$. 字串变换](https://www.acwing.com/problem/content/192/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
已知有两个字串 $A$, $B$ 及一组 **字串变换的规则**（至多 $6$ 个规则）:
|
|
|
$A_1→B_1$
|
|
|
$A_2→B_2$
|
|
|
…
|
|
|
|
|
|
规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $B_1$、$A_2$ 可以变换为 $B_2$…。
|
|
|
|
|
|
例如：$A$＝`abcd` $B$＝`xyz`
|
|
|
|
|
|
变换规则为：
|
|
|
|
|
|
`abc` → `xu` `ud` → `y` `y` → `yz`
|
|
|
|
|
|
则此时，$A$ 可以经过一系列的变换变为 $B$，其变换的过程为：
|
|
|
|
|
|
`abcd` → `xud` → `xy` → `xyz`
|
|
|
|
|
|
共进行了三次变换，使得 $A$ 变换为 $B$。
|
|
|
|
|
|
**输入格式**
|
|
|
输入格式如下：
|
|
|
|
|
|
$A ~ B$
|
|
|
$A_1 ~ B_1$
|
|
|
$A_2 ~ B_2$
|
|
|
… …
|
|
|
|
|
|
第一行是两个给定的字符串 $A$ 和 $B$。
|
|
|
|
|
|
接下来若干行，每行描述一组字串变换的规则。
|
|
|
|
|
|
所有字符串长度的上限为 $20$。
|
|
|
|
|
|
**输出格式**
|
|
|
若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$ ，则输出 **最少的变换步数**；否则输出 `NO ANSWER!`。
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
abcd xyz
|
|
|
abc xu
|
|
|
ud y
|
|
|
y yz
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
3
|
|
|
```
|
|
|
|
|
|
|
|
|
### 二、题目解析
|
|
|
|
|
|
**$bfs$的扩展方式**
|
|
|
* 枚举在原字符串中使用替换规则的起点
|
|
|
* 枚举所使用的的替换规则
|
|
|
|
|
|
|
|
|
很明显是 **最小步数模型**，我们先来分析一下单向起点开始$bfs$：
|
|
|
|
|
|
假设每次决策数量是 $K$，那么如果 **直接$bfs$** ，第一层是$1$,第二层是$K$，第三层是$K*K=K^2$,如果走十步，最坏情况下的搜索空间是 $K^{10}$，非常大，所以会$TLE$或者$MLE$。现在$K<=6$,那极限就是$6^{10}=60466176$,字符串大小上限为$20$,就是再乘上一个$20=60466176 \times 20 = 1209323520 ~byte = 1180980 kb=1153mb$
|
|
|
|
|
|
如果采用 **双向$bfs$**，则可以把 **搜索空间** 降到 $2 \times K^5$。在实际测试中只需 $20ms$ 左右，剪枝效果很好。
|
|
|
|
|
|
#### 双向$bfs$
|
|
|
在双向$bfs$时，每次**选择队列中元素数量较少的方向**来扩展。
|
|
|
|
|
|
#### 总结
|
|
|
* 一边扩展完了另一边还能扩展，说明不连通，达不到终状态
|
|
|
* 在枚举能替换的状态的时候用`substr`函数可以方便很多
|
|
|
* 写代码的时候压入队列扩展写一份即可，从起点扩展的方式和从终点扩展的方式是反过来的，一个是$a$变化到$b$,一个是变化$b$变化到$a$。
|
|
|
|
|
|
### 三、普通$bfs$
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
const int N = 10;
|
|
|
string a[N], b[N]; // 规则串，a[i]->b[i]
|
|
|
string A, B; // 原始串
|
|
|
queue<pair<string, int>> q; // bfs专用队列
|
|
|
unordered_set<string> st; // 是不是出现过
|
|
|
|
|
|
int n;
|
|
|
|
|
|
int bfs() {
|
|
|
q.push({A, 0}); // 字符串，变换次数
|
|
|
st.insert(A); // A串出现过
|
|
|
|
|
|
while (q.size()) {
|
|
|
auto u = q.front();
|
|
|
q.pop();
|
|
|
|
|
|
string t = u.first;
|
|
|
int d = u.second;
|
|
|
if (t == B) return d; // 找到，返回路径长度
|
|
|
|
|
|
for (int i = 0; i < t.size(); i++) { // 枚举字符串的每一位
|
|
|
for (int j = 0; j < n; j++) { // 枚举每个规则
|
|
|
if (t.substr(i, a[j].size()) == a[j]) {
|
|
|
string ts = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
|
|
|
if (st.count(ts) == 0) {
|
|
|
q.push({ts, d + 1});
|
|
|
st.insert(ts);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return INF;
|
|
|
}
|
|
|
|
|
|
// 通过了 9/10个数据
|
|
|
// 最后一个测试点挂掉
|
|
|
// 简单暴搜：超时
|
|
|
int main() {
|
|
|
cin >> A >> B;
|
|
|
while (cin >> a[n] >> b[n]) n++;
|
|
|
int ans = bfs();
|
|
|
if (ans > 10)
|
|
|
puts("NO ANSWER!");
|
|
|
else
|
|
|
printf("%d\n", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 四、双向广搜
|
|
|
```cpp {.line-numbers}
|
|
|
#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 bfs() {
|
|
|
// 两个串分别入队列
|
|
|
qa.push(A), qb.push(B);
|
|
|
da[A] = 0, db[B] = 0;
|
|
|
|
|
|
// 双向广搜套路
|
|
|
while (qa.size() && qb.size()) {
|
|
|
// 1、从qa中取
|
|
|
string u = qa.front();
|
|
|
qa.pop();
|
|
|
// 如果在b的扩展中出现过，则距离相加
|
|
|
if (db.count(u)) return da[u] + db[u];
|
|
|
|
|
|
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;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 2、从qb中取
|
|
|
u = qb.front();
|
|
|
qb.pop();
|
|
|
if (da.count(u)) return da[u] + db[u];
|
|
|
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 INF;
|
|
|
}
|
|
|
|
|
|
// 可以AC掉本题,16ms
|
|
|
int main() {
|
|
|
cin >> A >> B;
|
|
|
while (cin >> a[n] >> b[n]) n++;
|
|
|
|
|
|
int ans = bfs();
|
|
|
if (ans > 10)
|
|
|
puts("NO ANSWER!");
|
|
|
else
|
|
|
printf("%d\n", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
