洛谷 P1032 字串变换

题目描述

已知有两个字串 A, B 及一组字串变换的规则（至多6个规则）:

A1 -> B1

A2 -> B2

规则的含义为：在 A＄中的子串 A1 可以变换为 B1、A2 可以变换为 B2 …。

例如：A＝'abcd'B＝'xyz'

变换规则为：

‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

‘abcd’->‘xud’->‘xy’->‘xyz’

共进行了三次变换，使得 A 变换为B。

输入输出格式

输入格式：

输入格式如下：

A B

A1 B1 　　（变换规则）

A2 B2

... ...

所有字符串长度的上限为 20。

输出格式：

输出至屏幕。格式如下：

若在 10 步（包含 10步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出"NO ANSWER!"

输入输出样例

输入样例

abcd xyz
abc xu
ud y
y yz

输出样例

差不多是一道水题吧。。就是 bfs 暴搜就行。只不过在搜的时候要注意以下几点：

1.每一次是如何变换的

 1 string change(const string& now, int st, int num)    //now字符串第st位，第num条变换规则 
 2 {
 3     for(int i = 0; i < a1[num].length(); ++i)    
 4     {
 5         if(st + i >= now.length()) return "";      //若超出原字符串长度或 
 6         if(now[st + i] != a1[num][i]) return "";  //有一位不符合规则，就不能变换，返回空字符串 
 7     }
 8     string ret;
 9     //变换分三步 
10     for(int i = 0; i < st; ++i) ret += now[i];//1.将原字符串不用变换的前半部分复制下来 
11     ret += b1[num];                 //2.再加上变换部分 
12     for(int i = st + a1[num].length(); i < now.length(); ++i) ret += now[i];//3.加上原字符串剩下部分 
13     return ret;
14 }

用 string 的好处是，它支持加减运算，就是增加或减去某一字符串，而不用库里的 strcpy 函数。

2.再用bfs时，要记录之前的状态，防止又退回去，进入死循环。但这道题开 vis 数组就不太合适，因为每一个状态是一个字符串。所以最好开一个 map 来记录状态，并判重。

3.若按 2 的方法，因为是字符串的操作，大数据可能会超时，所以可以将字符串编码为 unsigned long long，一个简单的hash

1 ull hash(const string& now){
2     ull ret = 0;
3     for (int i = 0; i < now.length(); i++){
4         ret += now[i] - 'a' + 1; ret *= 27;
5     }
6     return ret;
7 }

完整代码

 1 #include <cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 typedef unsigned long long ull;
10 const int maxn = 25;
11 string a, b;
12 string a1[8], b1[8];
13 int cnt = 0;
14 ull hash(const string& now){
15     ull ret = 0;
16     for (int i = 0; i < now.length(); i++){
17         ret += now[i] - 'a' + 1; ret *= 27;
18     }
19     return ret;
20 }
21 string change(const string& now, int st, int num)
22 {
23     for(int i = 0; i < a1[num].length(); ++i)
24     {
25         if(st + i >= now.length()) return "";
26         if(now[st + i] != a1[num][i]) return "";
27     }
28     string ret;
29     for(int i = 0; i < st; ++i) ret += now[i];
30     ret += b1[num]; 
31     for(int i = st + a1[num].length(); i < now.length(); ++i) ret += now[i]; 
32     return ret;
33 }
34 map<ull, int>mp;    //相当于vis 
35 void bfs()
36 {
37     mp.clear();
38     queue<string>q;
39     q.push(a); mp[hash(a)] = 0;
40     while(!q.empty())
41     {
42         string now = q.front(); q.pop();
43         ull hn = hash(now);
44         if(mp[hn] >= 10) break;
45         for(int i = 0; i < cnt; ++i)
46         {
47             for(int j = 0; j < now.length(); ++j)
48             {
49                 string neww = change(now, j, i);
50                 ull hw = hash(neww);
51                 if(neww != "" && mp.find(hw) == mp.end())
52                 {
53                     q.push(neww); mp[hw] = mp[hn] + 1;
54                     if(neww  == b) {printf("%d
", mp[hw]); return;}
55                 }
56             }
57         }
58     }
59     printf("NO ANSWER!
");
60 }
61 int main()
62 {
63     cin >> a >> b;
64     while(cin >> a1[cnt] >> b1[cnt]) cnt++;
65     bfs();
66     return 0;
67 }

值得一提的是，这里的 map 发挥了两个作用，一个是 vis 数组，另一个是相当于记录步数的 dis数组