记录编号	277304	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2016-07-05 11:12:12	内存使用	0.45 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <ctime>
#include <fstream>
#include <queue>
using namespace std;
typedef unsigned long UL;
typedef struct AVLNode
{
	UL data;
	struct AVLNode *left;
	struct AVLNode *right;
	int height;
	int count;
}*pNode, *AVLTree;
pNode new_node()
{
	pNode d = (pNode)malloc(sizeof(AVLNode));
	memset(d, 0, sizeof(AVLNode));
	return d;
}
#define HEIGHT(d) (d?d->height:-1)
void maintain(pNode k)
{
	k -> height = max(HEIGHT(k -> left), HEIGHT(k -> right)) + 1;
}
pNode singleRotateLL(pNode k0)
{
	pNode k1 = k0 -> left;
	k0 -> left = k1 -> right;
	k1 -> right = k0;
	maintain(k0);
	maintain(k1);
	return k1;
}
pNode singleRotateRR(pNode k0)
{
	pNode k1 = k0 -> right;
	k0 -> right = k1 -> left;
	k1 -> left = k0;
	maintain(k0);
	maintain(k1);
	return k1;
}
pNode doubleRotateLR(pNode k0)
{
	k0 -> left = singleRotateRR(k0 -> left);
	return singleRotateLL(k0);
}
pNode doubleRotateRL(pNode k0)
{
	k0 -> right = singleRotateLL(k0 -> right);
	return singleRotateRR(k0);
}
pNode insert(AVLTree t, UL x)
{
	if(!t)
	{
		t = new_node();
		t -> data = x;
		t -> count = 1;
	}else if(x < t -> data)
	{
		t -> left = insert(t -> left, x);
		if(HEIGHT(t -> left) - HEIGHT(t -> right) == 2)
		{
			if(x < t -> left -> data)
				t = singleRotateLL(t);
			else
				t = doubleRotateLR(t);
		}
	}else if(x > t -> data)
	{
		t -> right = insert(t -> right, x);
		if(HEIGHT(t -> right) - HEIGHT(t -> left) == 2)
		{
			if(x > t -> right -> data)
				t = singleRotateRR(t);
			else
				t = doubleRotateRL(t);
		}
	}else
	{
		t -> count++;
	}
	maintain(t);
	return t;
}
int avlcount(AVLTree t, UL x)
{
	if(!t)
		return 0;
	if(x < t -> data)
		return avlcount(t -> left, x);
	else if(x > t -> data)
		return avlcount(t -> right, x);
	else
		return t -> count;
}
//
UL hash(const char *pstr)
{
	UL h = 0;
	UL x = 0;
	char *str = (char *)pstr;
	while(*str)
	{
		h = (h << 4)+(*str++);
		if((x = h & 0xF0000000L) != 0)
		{
			h ^= (x >> 24);
			h &= ~x;
		}
	}
	return h;
}
struct status
{
	string s;
	int step;
	status()
	{
		step = 0;
	}
};
struct transform
{
	string a, b;
}trans[10];
status S, T;
int transCount = 0;

int bfs()
{
	queue<status> q;
	AVLTree t = NULL;
	t = insert(t, hash(S.s.c_str()));
	q.push(S);
	while(q.size())
	{
		status now = q.front();
		q.pop();
		if(now.s == T.s)
			return now.step;
		if(now.step >= 10)
			return -1;
		for(int i = 0; i < transCount; i++)
		{
			int pos = 0;
			while(pos != -1)
			{
				status tmp = now;
				tmp.step++;
				pos = tmp.s.find(trans[i].a, pos);
				if(pos != -1)
				{
					tmp.s.replace(pos, trans[i].a.length(), trans[i].b);
					UL h = hash(tmp.s.c_str());
					if(!avlcount(t, h))
					{
						t = insert(t, h);
						q.push(tmp);
					}
					pos++;
				}
			}
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(false);
	ifstream III("string.in"); 
	ofstream OOO("string.out");
	#define cin III
	#define cout OOO
	cin >> S.s >> T.s;
	while(!cin.eof())
	{
		cin >> trans[transCount].a >> trans[transCount].b;
		transCount++;
	}
	int k = bfs();
	if(k != -1)
		cout << k;
	else
		cout << "NO ANSWER!";
	return 0;
}