[NOIP2002 提高组] 字串变换

题目背景

本题疑似错题，不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

题目描述

已知有两个字串 ,A,B 及一组字串变换的规则（至多 66 个规则），形如：

• 1→1A1​→B1​。
• 2→2A2​→B2​。

规则的含义为：在 A 中的子串 1A1​ 可以变换为 1B1​，2A2​ 可以变换为 2⋯B2​⋯。

例如：=abcdA=abcd，＝xyzB＝xyz，

变换规则为：

• abc→xuabc→xu，ud→yud→y，y→yzy→yz。

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

• abcd→xud→xy→xyzabcd→xud→xy→xyz。

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

输入格式

第一行有两个字符串 ,A,B。

接下来若干行，每行有两个字符串 ,Ai​,Bi​，表示一条变换规则。

输出格式

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

输入输出样例

abcd xyz
abc xu
ud y
y yz

3

说明/提示

对于 100%100% 数据，保证所有字符串长度的上限为 2020。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 unordered_map<string,int>mp;//无向图去重
 5 string st,ed,s1[10],s2[10];
 6 int res,n;
 7 void bfs(string st)
 8 {
 9     queue<string>que;//双端队列,一个是字符串,一个是次数
10     queue<int>num;
11     que.push(st),num.push(0);
12     while(!que.empty())
13     {
14         string now=que.front(),tmp=que.front(),tmp1=que.front();
15         int nownum=num.front();
16         que.pop(),num.pop();
17         if(mp.count(now)) continue;//剪枝
18         if(nownum>10)
19         {
20             cout<<"NO ANSWER!";
21             return;
22         }
23         if(now==ed)
24         {
25             cout<<nownum;
26             return;
27         }
28         mp[now]=1;
29         for(int i=0;i<res;i++)
30         {
31             now=tmp1;
32             while(1)
33             {
34                 int x=now.find(s1[i]);//寻找队头字符串是否可以被替换
35                 if(x==-1) break;//不行的话就断
36                 tmp=tmp1;
37                 tmp.replace(x,s1[i].size(),s2[i]);//把队头字符串中所有含有s1字符串的全替换了
38         //某个String a.replace(pos,len,另一个String b) 替换a中pos开始往后len的这些字符为b
39                 que.push(tmp),num.push(nownum+1);
40                 now[x]='~';//要把它变成没用字符,不然后下次while循环还是会搜到,会爆
41             } 
42         }
43     }
44     cout<<"NO ANSWER!";
45     return;
46 }
47 int main()
48 {
49     cin>>st>>ed;
50     while(cin>>s1[res]>>s2[res]) res++;
51     bfs(st);
52     return 0;
53 }