洛谷P1032 字串变换-题解

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

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

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

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<map>

 using namespace std;

 map<string,int>ma;

 struct mem {

     char s[];

     int step;

 } a,head;

 queue<mem>q;

 char to[],sta[][],ls[],end[][],le[];

 int i;

 char s[];

 int main() {

 //  freopen("testdata(1).in","r",stdin);

     cin>>a.s>>to;

     while(cin>>sta[i]>>end[i]) {

         ls[i]=strlen(sta[i]);

         le[i]=strlen(end[i]);

         i++;

     }

     i--;

     if(!strcmp(a.s,to)) {

         cout<<;

         return ;

     }

     q.push(a);

     ma[a.s]=;

     int l;

     while(!q.empty()) {

         head=q.front();

         q.pop();

         l=strlen(head.s);

         for(int j=; j<=i; j++)

             for(int k=; k<=l-ls[j]; k++) {

                 int x=strlen(s);

                 if((strncmp(head.s+k,sta[j],ls[j])==))

                     if((x-ls[j]+le[j])<=) {

                         strncpy(s,head.s,k);

                         strcpy(s+k,end[j]);

                         strcpy(s+k+le[j],head.s+k+ls[j]);

                         if(!strcmp(s,to)) {

                             cout<<head.step+;

                             return ;

                         }

                         if(!ma[s]&&head.step<) {

                             strcpy(a.s,s);

                             a.step=head.step+;

                             q.push(a);

                             ma[s]=;

                         }

                     }

             }

     }

     cout<<"NO ANSWER!";

 //    cout<<endl<<head.s;    //debug

     return ;

 }