洛谷 P1032 子串变换

题目链接 https://www.luogu.org/problemnew/show/P1032

本题是一道bfs问题，从a串开始，每一步完成替换一对字符串（但是一个一步替换可以将这对字符串替换好几次，比如a串是 ABCABCABCABC 一对替换是BC替换成ED，那么一步替换是将 ABCABCABCABC 替换成 AEDAEDAEDAED ）如果十步以内转换成b就输出

本题还让蒟蒻学习了一下map的用法真的十分好用 c++的stl真是A题利器

具体放代码吧：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 string a,b;
 6 string sa[10],sb[10];
 7 map<string,int>maps;  //用来判重，达到剪枝的效果
 8 queue<string>q;     //用来存转换出的字符串
 9 queue<int>nq;       //存当前的步数
10 int n,k=-1;
11 
12 void bfs()
13 {
14     int i;
15     while(!q.empty())      
16     {
17         if(nq.front()>10)      //超过十步，跳出循环
18         break;
19         if(q.front()==b)      
20         {
21             k=nq.front();    //到了b就更新k 跳出
22             break;
23         }
24         if(maps[q.front()]==1)        //如果当前的字符串搜索过，就pop掉 别忘了continue！
25         {
26             q.pop();
27             nq.pop();
28             continue;
29         }
30         maps[q.front()]=1;    //没有的话就标记上 起到剪枝的效果
31         
32         for(i=0;i<n;i++)
33         {
34             string s=q.front(),ss;
35              while(1)
36              {
37                  int m=s.find(sa[i]);   //寻找第一次出现sa[i]的位置
38                  if(m==-1) //找不到 说明能和sa[i]换的都换了 跳出while循环
39                  break;
40                  ss=q.front();
41                  ss.replace(m,sa[i].size(),sb[i]); 
42                  q.push(ss);
43                  nq.push(nq.front()+1);
44                  s[m]='#';   //将匹配的地方替换成一个不相关的字符，这样就可以找到下一个匹配的地方
45              }
46         }
47         q.pop();
48         nq.pop();
49     }
50     if(k==-1)
51     cout<<"NO ANSWER!";
52     else
53     cout<<k;
54 }
55 
56 
57 int main()
58 {
59     cin>>a>>b;
60     while(cin>>sa[n]>>sb[n])  //因为不知道会输入几个字符串，需要用while输入
61     n++;
62     q.push(a);
63     nq.push(0);
64     bfs();
65 }