【NOIP2002】字串变换
给你两个字符串 $A,B$ ，并给你 $n$ 个规则$(n\leq 6)$ ，求从 $A$ 到 $B$ 最小的变换步数（若$10$步内无法变换则无解，字符串长度不能超过$20$）。
解题思路：
从”$10$步内无法变换则无解” 则可以马上反应到：这是个搜索题（要素察觉）
既然是个搜索题，我们就要确定几点：搜索方式，搜索状态，搜索转移，搜索边界。
方式：这题是求最快的步数，所以我们采用 bfs 显然会比 dfs 快很多，而且有起点和终点状态我们就可以用双向搜索（具体不多说了），这里我们讲单向 bfs 的方法。
状态：首先，题目是对一个字符串进行操作，所以字符串显然是其中的一个状态
其次，题目中提到了对步数的限制，所以步数也是其中的一个状态。
1
2
3
4
| struct node {
int sum;
string s;
}
|
转移：其实题目中给的已经很明显了：就是按照这几种规则去转移当前字符串即可。
边界：题目中也有明显的指出，每次取出队头节点时要判断一下步数是否$ > 10$。
以上便是此题的基本思路，但是这题的代码及其繁琐，所以我们着重讲一讲代码的实现。
储存规则：规则是两个字符串，我们可以用一个pair<string,string>来储存。
转移：我们用的是string，在这里，我们可以使用stirng::find 和 string::replace来实现字串的替换。
特判：每次取出节点的时候判断一下步数，每次变换完判断一下长度是否超限。
由此，我们可以写出一份基本的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| vector<pair<string,string> > ma;
queue <node> s;
void bfs() {
node s = (node){a,0};
q.push(s);
while (!q.empty()) {
node p = q.front();q.pop();
string now = p.s;
int num = p.sum;
if (num > 10) continue;
for (int i = 0;i < tot;++i) {
string a1 = ma[i].first,b1 = ma[i].second;
if (now.find(a1) != std::string::npos) {
for (size_t j = now.find(a1);j != std::string::npos;j = now.find(a1,j+1)) {
string t = now;
t.replace(j,a1.length(),b1);
if (t == b) {cout << num+1;return ;}
if (t.length() <= 20) {
node pp = (node){t,num+1};
q.push(pp);
se.insert(t);
}
}
}
}
}
cout << "NO ANSWER!";
}
|
这份代码没什么问题，但是我们可以分析一下这个题目性质：
显然，一个串可以被几个不同的规则搜到，但是由于我们是 bfs 所以可以证明最开始搜到的那个情况是最优的，之后搜到的情况都可以直接舍弃。
所以，我们可以把用过的情况存在一个 map 里，如果这个情况搜过了就跳过。
1
2
3
4
5
6
7
| if (t.length() <= 20) {
if (se.find(t)==se.end()){
node pp = (node){t,num+1};
q.push(pp);
se.insert(t);
}
}
|
这样，你的代码就没什么问题了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ri register int
const int N = 100001;
const int M = 500001;
struct node {
string s;int sum;
};
vector<pair<string,string> > ma;
string a,b,a1,b1;
int ans,cnt,tot;
set <string> se;
queue <node> q;
void bfs() {
node s = (node){a,0};
q.push(s);
while (!q.empty()) {
node p = q.front();q.pop();
string now = p.s;
int num = p.sum;
if (num > 10) continue;
for (int i = 0;i < tot;++i) {
string a1 = ma[i].first,b1 = ma[i].second;
if (now.find(a1) != std::string::npos) {
for (size_t j = now.find(a1);j != std::string::npos;j = now.find(a1,j+1)) {
string t = now;
t.replace(j,a1.length(),b1);
if (t == b) {cout<<num+1;return ;}
if (t.length() <= 20) {
if (se.find(t)==se.end()){
node pp = (node){t,num+1};
q.push(pp);
se.insert(t);
}
}
}
}
}
}
cout << "NO ANSWER!";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> a >> b;
while (cin >> a1 >> b1) {
ma.push_back(make_pair(a1,b1));
++tot;
}
bfs();
return 0;
}
|