#include<cctype>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int abs(int a){return a<0?-a:a;}
inline int read()
{
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')b=-1;c=getchar();}
	while(isdigit(c)){a=(a<<3)+(a<<1)+(c^48);c=getchar();}
	return a*b;
}
inline void write(int a)
{
	if(a<0)putchar('-'),a=-a;
	if(a>9)write(a/10);
	putchar(a%10+48);
	return;
}
struct node{
	int ans;
	string s;
};
string a[10],b[10];
string s1,s2;
int cnt;
map<string,bool>mp;
void bfs()
{
	queue<node>que;
	node t;
	t.ans=0;
	t.s.assign(s1);
	mp[s1]=1;
	que.push(t);
	while(!que.empty())
	{
		t=que.front();
		que.pop();
		for(int i=0;i<t.s.size();i++)
		{
			for(int j=0;j<cnt;j++)
			{
				if(t.s[i]==a[j][0])
				{
					int x=i,y=0;
					bool bol=0;
					while(x<t.s.size()&&y<a[j].size())
					{
						if(t.s[x]!=a[j][y])
						{
							bol=1;
							break;
						}
						x++;
						y++;
					}
					if(bol==1)continue;
					string c;
					for(int k=0;k<i;k++)
						c.push_back(t.s[k]);
					for(int k=0;k<b[j].size();k++)
						c.push_back(b[j][k]);
					for(int k=i+a[j].size();k<t.s.size();k++)
						c.push_back(t.s[k]);
					if(mp.count(c)==1)continue;
					node q;
					mp[c]=1;
					q.ans=t.ans+1;
					q.s.assign(c);
					que.push(q);
					if(q.s==s2)
					{
						write(q.ans);
						puts("");
						return;
					}
				}
			}
		}
	}
	puts("NO ANSWER!");
	return;
}
int main()
{
	cin>>s1>>s2;
	while(cin>>a[cnt]>>b[cnt]&&!a[cnt].empty()&&!b[cnt].empty())cnt++;
	bfs();
	return 0;
}

本题第三个测试点类似于此

abc ab

a b

b a

为什么会超时？？蜜汁神奇