记录编号	2084	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2008-09-12 14:26:07	内存使用	0.26 MiB

#include <iostream>
#include <string>
#define MAX 50

using namespace std;

class treap
{
private:
	class node
	{
	public:
		node *left,*right;
		int v,fix;
		node(int tv)
		{
			v=tv;
			fix=rand();
			left=right=0;
		}
	};
	void rot_r(node *&p)
	{
		node *x=p->left;
		p->left=x->right;
		x->right=p;
		p=x;
	}
	void rot_l(node *&p)
	{
		node *x=p->right;
		p->right=x->left;
		x->left=p;
		p=x;
	}
	node *root;
	void _ins(node *&p,int v)
	{
		if (!p)
		{
			p=new node(v);
		}
		else if (v<p->v)
		{
			_ins(p->left,v);
			if (p->left->fix > p->fix)
				rot_r(p);
		}
		else
		{
			_ins(p->right,v);
			if (p->right->fix > p->fix)
				rot_l(p);
		}
	}
	bool _find(node *p,int v)
	{
		if (!p)
			return false;
		if (v==p->v)
			return true;
		if (v<p->v)
			return _find(p->left,v);
		if (v>p->v)
			return _find(p->right,v);
	}
public:
	treap()
	{
		srand(9112);
		root=0;
	}
	void ins(int v)
	{
		_ins(root,v);
	}
	bool find(int v)
	{
		return _find(root,v);
	}
};

typedef struct
{
	string s;
	int step;
}str;

class tqueue
{
public:
	class lkls
	{
	public:
		str p;
		lkls *next;
		lkls(str tp)
		{
			p=tp;next=0;
		}
	};
	lkls *first,*last;
	int size;
	tqueue()
	{
		size=0;
		first=last=0;
	}
	void ins(str p)
	{
		if (first)
			last=last->next=new lkls(p);
		else
			first=last=new lkls(p);
		size++;
	}
	str pop()
	{
		str rtn=first->p;
		lkls *t=first;
		first=first->next;
		delete t;
		size--;
		return rtn;
	}
};


str A,B;
string dicx[7],dicy[7];
int lx[7],ly[7];
int D;
treap Hash;
tqueue Q;

unsigned  int  ELFHash(const char * s)
{
	char *str=(char *)s;
	unsigned  int  hash  =  0 ;
	unsigned  int  x    =  0 ;
	while  ( * str)
	{
		hash  =  (hash  <<  4 )  +  ( * str ++ );
		if  ((x  =  hash  &  0xF0000000L )  !=  0 )
		{
			hash  ^=  (x  >>  24 );
			hash  &=  ~ x;
		}
	}
	return  (hash  &  0x7FFFFFFF );
}

void init()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin >> A.s >> B.s;
	A.step=B.step=0;
	Hash.ins(ELFHash(A.s.c_str()));
	while (!cin.eof())
	{
		cin >> dicx[D] >> dicy[D];
		lx[D]=dicx[D].length();
		ly[D]=dicy[D].length();
		if (lx[D]) D++;
	}
}

int bfs()
{
	str S,T;
	int i,pos;
	int hash;
	bool dup;
	Q.ins(A);
	while (Q.size)
	{
		T=Q.pop();
		if (T.s==B.s)
			return T.step;
		if (T.step==10)
			return -1;
		for (i=0;i<D;i++)
		{
			pos=0;
			while (pos!=-1)
			{
				S=T;
				S.step++;
				pos=S.s.find(dicx[i],pos);
				if (pos!=-1)
				{
					S.s.replace(pos,lx[i],dicy[i]);
					hash=ELFHash(S.s.c_str());
					dup=Hash.find(hash);
					if (!dup)
					{
						Hash.ins(hash);
						Q.ins(S);
					}
					pos++;
				}
			}
		}
	}
	return -1;
}

int main()
{
	int ans;
	init();
	ans=bfs();
	if (ans!=-1)
		cout << ans;
	else
		cout << "NO ANSWER!";
	return 0;
}