code1099 字串变换

BFS

听上去蛮简单的，实际编程复杂度较高（至少一个快睡着的人是这么认为的…）

抄的题解（感谢题解的作者<‘_’>）：

#include<queue>
#include<iostream>
#include<string>
#include<set>
using namespace std;struct node
{
    int step;
    string s;
    node(int step=,string s=""):step(step),s(s){}
};
set<string>c;
queue<node>q;
string st,end,a[],b[];
int n=,ans=-;int main()
{
    cin>>st>>end;
    node start(,st);
    q.push(start);
    c.insert(start.s);    while(cin>>a[n]>>b[n])n++;
    n--;    while(!q.empty())
    {
        node ing=q.front();
        q.pop();
        if(ing.s==end&&ing.step<=)
        {
            ans=ing.step;
            break;
        }
        if(ing.step>)break;
        for(int i=;i<=n;i++)
        {
            for(int j=;j<ing.s.length();j++)
            {
                int v=ing.s.find(a[i],j);
                   if(v>=)
                   {
                       node in=ing;
                       in.s.replace(v,a[i].length(),b[i]);
                    in.step++;
                          if(!c.count(in.s))
                    {
                        q.push(in);
                              c.insert(in.s);
                    }
                }
            }
        }
    }    if(ans!=-)cout<<ans;
    else cout<<"NO ANSWER!";    return ;
}