洛谷P1032 字串变换-题解

https://www.luogu.org/problemnew/show/P1032--(题目传送）

好在数据范围很小，暴力一点也能过。思路较简单，按照所有规则，从第一位开始广搜。

注意：1.strcpy可能会造成内存溢出。2.字符串被调用/初始化前对它求长度无意义（会产生奇妙的反应）

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<map>
 6 using namespace std;
 7 map<string,int>ma;
 8 struct mem {
 9     char s[22];
10     int step;
11 } a,head;
12 queue<mem>q;
13 char to[22],sta[7][22],ls[7],end[7][22],le[7];
14 int i;
15 char s[22];
16 int main() {
17 //  freopen("testdata(1).in","r",stdin);
18     cin>>a.s>>to;
19     while(cin>>sta[i]>>end[i]) {
20         ls[i]=strlen(sta[i]);
21         le[i]=strlen(end[i]);
22         i++;
23     }
24     i--;
25     if(!strcmp(a.s,to)) {
26         cout<<0;
27         return 0;
28     }
29     q.push(a);
30     ma[a.s]=1;
31     int l;
32     while(!q.empty()) {
33         head=q.front();
34         q.pop();
35         l=strlen(head.s);
36         for(int j=0; j<=i; j++)
37             for(int k=0; k<=l-ls[j]; k++) {
38                 int x=strlen(s);
39                 if((strncmp(head.s+k,sta[j],ls[j])==0))
40                     if((x-ls[j]+le[j])<=20) {
41                         strncpy(s,head.s,k);
42                         strcpy(s+k,end[j]);
43                         strcpy(s+k+le[j],head.s+k+ls[j]);
44                         if(!strcmp(s,to)) {
45                             cout<<head.step+1;
46                             return 0;
47                         }
48                         if(!ma[s]&&head.step<10) {
49                             strcpy(a.s,s);
50                             a.step=head.step+1;
51                             q.push(a);
52                             ma[s]=1;
53                         }
54                     }
55             }
56     }
57     cout<<"NO ANSWER!";
58 //    cout<<endl<<head.s;    //debug
59     return 0;
60 }