20分代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
	string s;
	int step;
};
struct changes
{
	string a,b;
}l[100010];
int n=1;
string s2;
void bfs(string s)
{
	queue<node>q;
	node h,t;
	h.s=s,h.step=0;
	q.push(h);
	while(!q.empty())
	{
		h=q.front(),q.pop();
		if(h.step==-1||h.s==s2)
		{
			cout<<h.step;
			return;
		}
		for(int i=1;i<=n;i++)
		{
			if(h.s.find(l[i].a,0)!=string::npos)
			{
				int left=h.s.find(l[i].a,0),right=h.s.find(l[i].a)+l[i].a.length();
				t.s=h.s.substr(0,left)+l[i].b+s.substr(right,h.s.length()-right),t.step=h.step+1;
				if(t.step>10) t.step=-1;
				q.push(t);
			}
		}
	}
}
int main()
{
	string s;
	cin>>s>>s2;
	while(cin>>l[n].a)
	{
		cin>>l[n].b;
		n++;
	}
	bfs(s);
	return 0;
}

0分代码(在二十分的基础上改写的代码)

#include <bits/stdc++.h>
using namespace std;
struct node
{
	string s;
	int step;
};
struct changes
{
	string a,b;
}l[1000010];
unordered_map<string,bool>m;
int n=1;
string s2;
int minstep=INT_MAX;
void bfs(string s)
{
	queue<node>q;
	node h,t;
	h.s=s,h.step=0;
	q.push(h);
	while(!q.empty())
	{
		h=q.front(),q.pop();
		if(h.s==s2)
		{
			minstep=min(minstep,h.step);
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			if(h.s.find(l[i].a,0)!=string::npos)
			{
				int left=h.s.find(l[i].a,0),right=h.s.find(l[i].a)+l[i].a.length()+1;
				t.s=h.s.substr(0,left)+l[i].b+s.substr(right,h.s.length()-right-1),t.step=h.step+1;
				if(!m[t.s])
				{
					q.push(t);
					m[t.s]=1;
				}
			}
		}
	}
}
int main()
{
	string s;
	cin>>s>>s2;
	while(cin>>l[n].a)
	{
		cin>>l[n].b;
		n++;
	}
	bfs(s);
	if(minstep>10) cout<<"NO ANSWER!";
	else cout<<minstep;
	return 0;
}