记录编号	38975	评测结果	AAAAAAAAAA
题目名称	基因重组	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.526 s
提交时间	2012-07-03 12:12:56	内存使用	76.60 MiB

#include <cstdlib>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int Base=4;
const int MAXN=13;
typedef char array[MAXN];
array gene;
int N,start,goal;
int cyou[20000000];

inline int power(int base,int pow)
{
	int res=1;
	for(int i=1;i<=pow;i++) res*=base;
	return res;
}

inline int getnum(char a)
{
	switch(a)
	{
	case'A':return 0;break;
	case'C':return 1;break;
	case'G':return 2;break;
	case'T':return 3;break;
	default:return -1;break;
	}
	return -1;
}

inline int gethash(array tmp)
{
	int res=0;
	for(int i=0;i<N;i++)
		res+=power(Base,i)*getnum(tmp[i]);
	return res;
}


inline void init()
{
	scanf("%d\n",&N);
	scanf("%s\n",gene);
	start=gethash(gene);
	//printf("%d\n",start);
	scanf("%s\n",gene);
	goal=gethash(gene);
	//printf("%d\n",goal);
	if(start==goal)
	{
		printf("0\n");
		exit(0);
	}
	cyou[start]=1;
}


inline void getgene(array &tmp,int has)
{
	int top=0,modder;
	while(top<N)
	{
		modder=has%Base;
		switch(modder)
		{
		case 0:tmp[top]='A';break;
		case 1:tmp[top]='C';break;
		case 2:tmp[top]='G';break;
		case 3:tmp[top]='T';break;
		}
		top++;
		has=(has-modder)/Base;
	}
}

class QUEUE
{
public:
	int has,times;
};
queue<QUEUE> q;

inline void bfs()
{
	q.push((QUEUE){start,0});
	int th,nh,tt,nt;
	QUEUE tmp;
	array tgene;
	while(q.size())
	{
		tmp=q.front(); q.pop();
		th=tmp.has;  tt=tmp.times;
		getgene(gene,th);
		
		//swap1
		for(int i=0;i<N;i++) tgene[i]=gene[i];
		char ttt=tgene[0];
		tgene[0]=tgene[1]; 
		tgene[1]=ttt;
		nh=gethash(tgene); nt=tt+1;
		if(nh==goal)
		{
			printf("%d\n",nt);
			return;
		}
		if(!cyou[nh])
		{
			q.push((QUEUE){nh,nt});
			cyou[nh]=1;
		}
		
		
		//swap2
		for(int i=0;i<N;i++) tgene[i]=gene[i];
		ttt=tgene[0];
		for(int i=0;i<N-1;i++) tgene[i]=tgene[i+1];
		tgene[N-1]=ttt;
		nh=gethash(tgene); nt=tt+1;
		if(nh==goal)
		{
			printf("%d\n",nt);
			return;
		}
		if(!cyou[nh])
		{
			q.push((QUEUE){nh,nt});
			cyou[nh]=1;
		}
	}
}

int main()
{
	freopen("genea.in","r",stdin);
	freopen("genea.out","w",stdout);
	init();
	bfs();
	return 0;
}