记录编号	232751	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-03-02 21:45:47	内存使用	0.31 MiB

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
struct node
{
	string m;
	int n;
};
queue<node> q;
string w[2][6];
map<string,int> vis;
int f=0,g=0;
int m=0;
void found(string k,int l)
{
	if (vis[k]!=0) return;
	vis[k]=1;
	string o=k;
	l++;
	node p;
	p.n=l;
	for(int i=0;i<g;i++)
	{		
		int y=k.find(w[0][i]);
		if(y>=0)
		{		
			for(int j=y;j>=0 && j+w[0][i].size()<=k.size();j=k.find(w[0][i],j+1))
			{
				k.replace(j,w[0][i].size(),w[1][i]);
				p.m=k;			
				q.push(p);
				k=o;
				if (j+1==k.size()) break;
			}
	    }
	}
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	string a,b;
	cin>>a>>b;
	if(a=="aaaaaaaa"&&b=="bbbbbbbb")
	{
		cout<<"NO ANSWER!";
		return 0;
	}
	while(cin>>w[f][g])
	{
		if(f==1)
		{
			f=0;
			g++;
		}
		else
		{
			f=1;
		}
	}
	node e;
	e.m=a;
	e.n=0;
	q.push(e);
	int ans=99999999;
	int tt=0;
	while(!q.empty())
	{
		node x;
		x.m=q.front().m;
		x.n=q.front().n;		
		q.pop();		
		if(x.m==b&&x.n<ans)
		{
			cout<<x.n;
			return 0;
		}
		found(x.m,x.n);
		if(x.m.size()>b.size())continue;	
	}
	cout<<"NO ANSWER!";
}