[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!。
输入输出样例
输入 #1
abcd xyz abc xu ud y y yz
输出 #1
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 }