记录编号	39036	评测结果	WWWWWWWWWW
题目名称	基因重组	最终得分	0
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	0.354 s
提交时间	2012-07-03 17:10:41	内存使用	4.20 MiB

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int n,begin,end,ans,tot;
int hash[1000000],a[13],b[13],q[10001][2];
set<int> done;
void get(int u) {
	int t = n;
	while (t) {
		a[t] = u % 4;
		t--;
		u /= 4;
	}
}
	
int main() {
	freopen("genea.in","r",stdin);
	freopen("genea.out","w",stdout);
	scanf("%d\n", &n);
	char ch;
	for (int i = 1;i <= n;i++) {
		ch = getchar();
		if (ch == 'A') a[i] = 0;
		if (ch == 'C') a[i] = 1;
		if (ch == 'G') a[i] = 2;
		if (ch == 'T') a[i] = 3;
		begin = begin * 4 + a[i];
	}
	ch = getchar();
	for (int i = 1;i <= n;i++) {
		ch = getchar();
		if (ch == 'A') b[i] = 0;
		if (ch == 'C') b[i] = 1;
		if (ch == 'G') b[i] = 2;
		if (ch == 'T') b[i] = 3;
		end = end * 4 + b[i];
	}
	q[0][0] = begin;
	done.insert(begin);
	int head = 0,tail = 1;
	while (head != tail) {
		int now = q[head][0];
		// 1302 
		if (now == end) {
			ans = q[head][1];
			break;
		}
		get(now);
		std::swap(a[1],a[2]);
		int o = 0;
		for (int i = 1;i <= n;i++) 
			o = o * 4 + a[i];
		if (!done.count(o)) {
			done.insert(o);
			if (tail > 10000) tail = 0;
			q[tail][0] = o;q[tail][1] = q[head][1] + 1;
			tail++;
		}
		std::swap(a[1],a[2]);
		o = 0;
		for (int i = 2;i <= n;i++)
			o = o * 4 + a[i];
		o = o * 4 + a[1];
		if (!done.count(o))  {
			done.insert(o);
			if (tail > 10000) tail = 0;
			q[tail][0] = o;q[tail][1] = q[head][1] + 1;
			tail++;
		}
		head++;
		if (head > 10000) head = 0;
	}
	printf("%d\n", ans);
	return 0;
}