NOIP2002提高组T2：字符串变换

题目链接

���符串变换

题目描述

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

A 1 → B 1 A_1→B_1 A1​→B1​

A 2 → B 2 A_2→B_2 A2​→B2​

…

规则的含义为：在 A A A中的子串 A 1 A_1 A1​ 可以变换为 B 1 B_1 B1​、 A 2 A_2 A2​可以变换为 B 2 B_2 B2​…。

例如： A = A= A=abcd， B = B= B=xyz

变换规则为：

abc → xu，ud → y，y → yz

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

，其变换的过程为：

abcd → xud → xy → xyz

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

注意，一次变换只能变换一个子串，例如 A ＝ A＝ A＝=aa， B = B= B=bb

变换规则为：

a → b

此时，不能将两个 a 在一步中全部转换为 b，而应当分两步完成。

输入格式

A    B A~~B A  B

A 1   B 1 A_1~B_1 A1​ B1​

A 2   B 2 A_2~B_2 A2​ B2​

… …

第一行是两个给定的字符串 A A A和 B B B。

接下来若干行，每行描述一组字串变换的规则。

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

输出格式

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

输入样例

abcd xyzabc xuud yy yz

输出样例

3

算法思想

根据题目描述，通过输入的规则将字串 A A A变换为 B B B，求最小步数，显然可以通过BFS求解。

朴素版广搜

分析数据范围，至多 6 6 6个规则，在 10 10 10 步（包含 10 10 10步）以内进行转换，如果直接进行BFS，在最坏情况下搜索的状态空间大约是 6 10 = 60 , 466 , 176 6^{10}=60,466,176 610=60,466,176，可以满足题目要求。

算法实现

• 将起始字符串 A \text{A} A加入队列
• 只要队列不空，重复下面的处理：
  • 从队首取出一个字符串 s \text{s} s
  • 如果变换到 s \text{s} s的步数超过 10 10 10，则无解，并结束搜索
  • 从 1 ∼ n 1\sim n 1∼n枚举变换规则 a i → b i a_i\rightarrow b_i ai​→bi​
    • 只要字符串 s \text{s} s中包含 a i a_i ai​
      • 将其替换为 b i b_i bi​，得到替换之后的字符串 t \text{t} t
      • 如果替换后等于字符串 B \text{B} B，则搜索结束，返回变换步数
      • 如果字符串 t \text{t} t之前没有出现过，将其加入队列
      • 从下一个位置继续查找 a i a_i ai​

        代码实现

        #include #include #include using namespace std;const int N = 7;string a[N], b[N];string A, B;int n;int bfs(){    unordered_map dis; //记录搜到到字符串的最小步数    queue q;    dis[A] = 0;    q.push(A);    int ans = 0;    while(q.size())    {        string s = q.front(); q.pop();        if(dis[s] >= 10) { return -1; } //超过10步，返回-1        for(int i = 0; i > A >> B;    while(cin >> a[n] >> b[n]) n ++;    int ans = bfs();    if(ans == -1) puts("NO ANSWER!");    else cout     int d = da[q.front()]; //层数    while(q.size() && da[q.front()] == d) //将同层的节点全部扩展    {        string s = q.front(); q.pop();        for(int i = 0; i > B;    while(cin >> a[n] >> b[n]) n ++;    int t = bfs();    if(t == -1) puts("NO ANSWER!");    else cout