1390 - 密码锁
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。
题目输入
第一行输入N，第二行输入N个数字，只包含0，1，2
题目输出
输入/输出样例
题目输入
5 02120 5 02120
题目输出
1 1
C语言解答
#include<stdio.h> #include<string.h> int v[2000000],q[2000000]; int n; int a[16]; int valid(int a[],int n) { int i; for(i=0;i+4<=n;i++) if (a[i]==2 && a[i+1]==0 && a[i+2]==1 && a[i+3]==2) return 1; return 0; } int trans1(int a[],int n) { int ret=0,i; for(i=0;i<n;i++) ret=ret*3+a[i]; return ret; } void trans2(int a[],int n,int m) { int i; for(i=n-1;i>=0;i--) { a[i]=m%3; m/=3; } } int main() { char str[16]; int i,j,t,m,tmp; memset(v,0xff,sizeof(v)); while(scanf("%d",&n)!=EOF) { scanf("%s",str); for(i=0;i<n;i++) a[i]=str[i]-'0'; m=trans1(a,n); v[m]=t=0,q[t++]=m; for(i=0;i<t;i++) { trans2(a,n,q[i]); if (valid(a,n)) break; for(j=0;j<n-1;j++) { tmp=a[j],a[j]=a[j+1],a[j+1]=tmp; m=trans1(a,n); if (v[m]<0) { v[m]=v[q[i]]+1; q[t++]=m; } tmp=a[j],a[j]=a[j+1],a[j+1]=tmp; } } if (i<t) printf("%d\n",v[q[i]]); else puts("-1"); for(i=0;i<t;i++) v[q[i]]=-1; } return 0; }
C++解答
#include<stdio.h> #include<string.h> int v[2000000],q[2000000]; int n; int a[16]; int valid(int a[],int n) { int i; for(i=0;i+4<=n;i++) if (a[i]==2 && a[i+1]==0 && a[i+2]==1 && a[i+3]==2) return 1; return 0; } int trans1(int a[],int n) { int ret=0,i; for(i=0;i<n;i++) ret=ret*3+a[i]; return ret; } void trans2(int a[],int n,int m) { int i; for(i=n-1;i>=0;i--) { a[i]=m%3; m/=3; } } int main() { char str[16]; int i,j,t,m,tmp; memset(v,0xff,sizeof(v)); while(scanf("%d",&n)!=EOF) { scanf("%s",str); for(i=0;i<n;i++) a[i]=str[i]-'0'; m=trans1(a,n); v[m]=t=0,q[t++]=m; for(i=0;i<t;i++) { trans2(a,n,q[i]); if (valid(a,n)) break; for(j=0;j<n-1;j++) { tmp=a[j],a[j]=a[j+1],a[j+1]=tmp; m=trans1(a,n); if (v[m]<0) { v[m]=v[q[i]]+1; q[t++]=m; } tmp=a[j],a[j]=a[j+1],a[j+1]=tmp; } } if (i<t) printf("%d\n",v[q[i]]); else puts("-1"); for(i=0;i<t;i++) v[q[i]]=-1; } return 0; }