记录编号	67027	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	老师好~~~	是否通过	通过
代码语言	C++	运行时间	4.435 s
提交时间	2013-08-07 10:37:26	内存使用	1.08 MiB

#include<fstream>
#include<deque>
#include<string>
#include<cstdlib>
#include<set>
using namespace std;
ifstream fin("string.in");
ofstream fout("string.out");
deque<string> b;
string s1,s2;
int G=0;
class woca
{
public:
	string x;
	string y;
}a[100000];
class woqu
{
public:
	int x;
	string y;
};
set<woqu> ctr;
set<woqu>::iterator cp;
int K=1,co=1;
/*string flag[100000];*/
/*int e[100000];*/
bool operator<(woqu m,woqu n)
{
	if(m.y<n.y)
		return 1;
	else
		return 0;
}
bool operator==(woqu m,woqu n)
{
	if(m.y==n.y)
		return 1;
	else
		return 0;
}
void BFS()
{
	int l,s,i,k,m,jicun;
	string j;
	string temp;
	while(b.size()!=0)
	{
		j=b.at(0);
	    b.pop_front();
	    l=j.length();
	    for(i=1;i<=K;i++)
	  {
		s=a[i].x.length();
		for(k=0;k<=l-s;k++)
		{
			if(a[i].x==j.substr(k,s))
			{
 				temp=j.substr(0,k)+a[i].y+j.substr(k+s,l-k-s);
				woqu ttt,ttt1;
				ttt.y=temp;
				if(ctr.find(ttt)==ctr.end())
				{
			    b.push_back(temp);
				ttt1.y=j;
				cp=ctr.find(ttt1);//向平衡二叉树中查找父亲节点
				/*for(m=1;m<=co;m++)
				{
					if(flag[m]==j)
						jicun=e[m];
				}*/
				/*co++;
				flag[co]=temp;
				e[co]=jicun+1;*/
				co=(*cp).x+1;
				ttt.x=co;
				ctr.insert(ttt);//向平衡二叉树中插入元素
				if(co>10)
				{
					fout<<"NO ANSWER!";
					G=1;
					return;
				}
				if(temp==s2)
				{
			       fout<<co;
				   G=1;
			        return ;
				}
				}
			}
		}
	  }
	}
}
int main()
{
	int i;
	fin>>s1>>s2;
	while(!fin.eof())
	{
		fin>>a[K].x>>a[K].y;
		if(a[K].x.length()!=0&&a[K].y.length()!=0)
			K++;
	}
	K--;
	woqu ll;
	ll.y=s1;
	ll.x=0;
	b.push_back(s1);
	ctr.insert(ll);
	BFS();
	if(G==0)
		fout<<"NO ANSWER!"<<endl;
	return 0;
}