洛谷 P1032 字串变换 题解

每日一题 day19 打卡

Analysis

广搜+map判重

用find寻找字串，再用replace替换字串

这里的map相当于正常广搜的一个book的作用

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<map>

 #define int long long

 #define maxn 6+10

 using namespace std;

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 string a,b;

 string ca[maxn],cb[maxn];

 map<string,int> m;

 int len=;

 queue<string> cq;

 queue<int> sq;

 inline int bfs()

 {

     while(!cq.empty()&&cq.front()!=b&&sq.front()<=)

     {

         if(m[cq.front()]==)

         {

             cq.pop();

             sq.pop();

             continue;

         }

         m[cq.front()]=;

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

         {

             string ns=cq.front();

             while()

             {

                 int site=ns.find(ca[i]);

                 if(site==-) break;

                 string ss=cq.front();

                 ss.replace(site,ca[i].size(),cb[i]);

                 cq.push(ss);

                 sq.push(sq.front()+);

                 ns[site]='#';

             }

         }

     }

     if(cq.empty()||sq.front()>) return -;

     else return sq.front();

 }

 signed main()

 {

     cin>>a>>b;

     while(cin>>ca[len]>>cb[len]) len++;

     len--;

     if(len==&&a!=b)

     {

         cout<<"NO ANSWER!";

         return ;

     }

     cq.push(a);

     sq.push();

     int ans=bfs();

     if(ans==-) cout<<"NO ANSWER!";

     else write(ans);

     return ;

 }

请各位大佬斧正