题目1482：玛雅人的密码

题目描述：

玛雅人有一种密码，如果字符串中出现连续的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;  
}