题解：P1032 [NOIP 2002 提高组] 字串变换

#include<bits/stdc++.h>
using namespace std;
string be,en;
set<string> st;
map<string,vector<string>> mp;
map<string,bool> mp1;
int minn=0x3f3f3f3f;
int n=0;
struct node{
    string sss;
    int cs;
};
inline void bfs()
{
	queue<node> q;
    q.push(node{be,0});
    mp1[be]=1;
    while(!q.empty())
    {
        string s=q.front().sss;
        int i=q.front().cs;
        q.pop();
        if(i>=10)continue;
    	if(s==en)
    	{
    		minn=min(minn,i);
    		break;
    	}
    	for(auto x:st)
    	{
            for(int k=0;k+x.size()-1<s.size();k++)
    		{
    			string ss=s;
                if(s.substr(k,x.size())!=x)continue;
    			int tmp=k;
    			ss.erase(tmp,x.size());
    			for(auto t:mp[x])
    			{
    				string ssss=ss;
    				ssss.insert(tmp,t);
    				if(mp1[ssss])continue;
                    // if(i==0)cout<<sss<<endl;
    				mp1[ssss]=1;
                    q.push(node{ssss,i+1});
    			}
    		}
    	}
    }
}
int main()
{
	cin>>be>>en;
	string x,y;
	while(cin>>x>>y)
	{
		n++;
		st.insert(x);
        mp[x].push_back(y);
	}
	bfs();
	if(minn==0x3f3f3f3f)cout<<"NO ANSWER!";
	else cout<<minn;
	return 0;
 }