学步园

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

题意要求通过移位使得出现连续的2012四个数字，搜索题，只是搜索状态不好发现，总共的所搜状态顶多3^13=1594323，开辟hash[1594323]；所以使用搜索不会超时。

关键在于“当前状态字符串“转换成相应的状态hash值，从而可以具体实施搜索。

程序代码如下：

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N=1600000;
bool used[N];
int n;

typedef struct Node
{
	int num,cnt;
	char arr[14];
}Node;
queue<Node> Q;

void swap(char *str,int i, int j)
{
	int temp=str[i];
	str[i]=str[j];str[j]=temp;
}

bool test(char *str)
{
	for(int i=0;i<=n-4;i++)
	{
		if(str[i]=='2'&&str[i+1]=='0'&&str[i+2]=='1'&&str[i+3]=='2')
			return true;
	}
	return false;
}

int stringToInt(char *str)
{
	int res=0;
	for(int i=0;str[i];i++)
	{
		res=3*res+str[i]-'0';
	}
	return res;
}

int bfs()
{
	while(!Q.empty())
	{
		Node temp=Q.front();
		int cnt=temp.cnt;
		Q.pop();
		if(test(temp.arr))
			return temp.cnt;
		for(int i=0;i<n-1;i++)
		{
			swap(temp.arr,i,i+1);
			int num=stringToInt(temp.arr);
			if(!used[num])
			{
				used[num]=true;
				Node temp1;
				temp1.cnt=cnt+1;
				strcpy(temp1.arr,temp.arr);
				temp1.num=num;
				Q.push(temp1);
				swap(temp.arr,i,i+1);
			}
			else
				swap(temp.arr,i,i+1);
		}
	}
	return -1;
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		char str[14];
		scanf("%s",str);
		if(n<4)
		{
			printf("-1\n");
			continue;
		}
		memset(used,0,sizeof(used));
		while(!Q.empty())
			Q.pop();
		Node node;
		int num=stringToInt(str);
		used[num]=true;
		node.num=num,node.cnt=0;strcpy(node.arr,str);
		Q.push(node);
		int res=bfs();
		printf("%d\n",res);
	}
	return 0;
}