记录编号	39028	评测结果	AWAAAAAWAA
题目名称	基因重组	最终得分	80
用户昵称	ZhouHang	是否通过	未通过
代码语言	C++	运行时间	1.515 s
提交时间	2012-07-03 16:13:23	内存使用	16.31 MiB

/**
*Prob	: genea
*Data	: 2012-7-3
*Sol	: Search + hash
*/

#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
#include <cstring>

#define MaxS 16777216

using namespace std;

struct node {
	int k,s;
};
queue <node> list;

int n; 
bool v[MaxS];
char tma[20],tmb[20];
int a[20],b[20],tm1[20],tm2[20],tmp[20];

void Change_init()
{
	int tmp = 1; a[n] = b[n] = 0;
	for (int i=n-1; i>=0; i--) {
		a[n] += a[i]*tmp;
		b[n] += b[i]*tmp;
		tmp *= 4;
	}
}
void Change(int *a)
{
	int tmp = 1; a[n] = 0;
	for (int i=n-1; i>=0; i--) {
		a[n] += a[i]*tmp;
		tmp *= 4;
	}
}
void Change1(int *tm1)
{
	int tmp = tm1[0];
	tm1[0] = tm1[1]; tm1[1] = tmp;
}
void Change2(int *tm2)
{
	int tmp = tm2[0];
	for (int i=0; i<n-1; i++)
		tm2[i] = tm2[i+1];
	tm2[n-1] = tmp;
}
void Change3(int s,int *tmp)
{
	tmp[n] = s; int num = n;
	memset(tmp,0,sizeof(tmp));
	while (s) {
		num--;
		tmp[num] = s%4;
		s /= 4;
	}
}

int Search()
{
	memset(v,false,sizeof(v));
	node now,nowtm1,nowtm2;
	now.k = 0; now.s = a[n];
	list.push(now);
	v[a[n]] = true;
	
	while (!list.empty()) {
		now = list.front();
		list.pop();
		Change3(now.s,tmp);
		for (int i=0; i<=n; i++)
			tm2[i] = tm1[i] = tmp[i];
		Change1(tm1); Change(tm1);
		Change2(tm2); Change(tm2);
		if (tm1[n]==b[n]||tm2[n]==b[n])
			return now.k+1;
		if (!v[tm1[n]]) {
			v[tm1[n]] = true;
			nowtm1.k = now.k+1;
			nowtm1.s = tm1[n];
			list.push(nowtm1);
		}
		if (!v[tm2[n]]) {
			v[tm2[n]] = true;
			nowtm2.k = now.k+1;
			nowtm2.s = tm2[n];
			list.push(nowtm2);
		}
	}
	
}

int main()
{
	freopen("genea.in","r",stdin);
	freopen("genea.out","w",stdout);
	
	scanf("%d",&n);
	scanf("%s",&tma);
	scanf("%s",&tmb);
	for (int i=0; i<n; i++) {
		if (tma[i]=='A') a[i] = 0; 
		if (tma[i]=='C') a[i] = 1; 
		if (tma[i]=='G') a[i] = 2; 
		if (tma[i]=='T') a[i] = 3; 

		if (tmb[i]=='A') b[i] = 0; 
		if (tmb[i]=='C') b[i] = 1; 
		if (tmb[i]=='G') b[i] = 2; 
		if (tmb[i]=='T') b[i] = 3; 
	}
	Change_init();
	
	int ans;
	if (a[n]==b[n]) ans = 0;
	else ans=Search();
	
	printf("%d\n",ans);
	
	fclose(stdin); fclose(stdout);
	return 0;
}