【题解】洛谷P1032 [NOIP2002TG]字串变换（BFS+字符串）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
#define maxn 15
map<string,int> m;//map用来判重 
string a,b;
string c[maxn],d[maxn];
int n,ans;
struct node//自定义结构体方便调用 
{
    string str;//字符串 
    int sum;//步数 
};
queue <node> q;//队列 
string change(const string &str,int i,int j)
{
    string t="";
    if(i+c[j].length()>str.length()) return t;//长度超过就不可以替换 
    for(int k=0;k<c[j].length();k++)//枚举判断是否可以替换 
        if(str[i+k]!=c[j][k]) return t; 
    t=str.substr(0,i);//新串的前面没有改变 
    t+=d[j];//加上替换之后的串 
    t+=str.substr(i+c[j].length());//加上需要替换的串的后面不需要替换的串 
    return t;
}
int main()
{
    cin>>a>>b;
    while(cin>>c[n]>>d[n]) n++;//毒瘤输入 
    node s;
    s.str=a;//初始的串 
    s.sum=0;
    q.push(s);
    while(!q.empty())//BFS 
    {
        node x=q.front();//取出队列头 
        q.pop();//删除头 
        string temp;
        if(m.count(x.str)==1) continue;//判重 
        if(x.str==b) //如果已经满足 
        {
            ans=x.sum;
            break;
        }
        m[x.str]=1;//这种字符串已经尝试过 
        for(int i=0;i<x.str.length();i++)//从头枚举哪里可以替换 
        {
            for(int j=0;j<n;j++)//枚举替换方案 
            {
                temp=change(x.str,i,j);//替换 
                if(temp!="")//如果可以替换 
                {
                    node y;//加入队列 
                    y.str=temp;
                    y.sum=x.sum+1;
                    q.push(y);
                }
            }
        }
    }
    if(ans>10||(!ans))//注意ans同样不能为0 
    cout<<"NO ANSWER!";
    else
    cout<<ans;
}