[cpp] #include<stdio.h> #include<string.h> #include<queue> #define MAXS 20 using namespace std; bool mark[1594330]; int mark2[3]; int l,n; typedef struct E{ int h[MAXS]; int num;//映射成三進制的十進制以便harsh int count;//記錄轉換次數 void change()//轉換成三進制數- -！ { num=0; int i,j; for(i=0,j=1;i<n;i++,j*=3)num+=h[i]*j; } }E; E a,temp; queue < E > Q; bool check(E x) { int i; for(i=0;i<n;i++)//因為數組後面全是0。所以判定條件不用i<n-3。因為到最後必然false。 { if(x.h[i]==2&&x.h[i+1]==0&&x.h[i+2]==1&&x.h[i+3]==2)return true; } return false; } int main() { int i,j,ans;//ans記錄一共的次數 char temph[MAXS]; while(~scanf("%d",&n)) { mark2[0]=mark2[1]=mark2[2]=ans=0; memset(mark,0,sizeof(mark)); memset(&a,0,sizeof(a)); while(Q.empty()==false)Q.pop(); getchar(); scanf("%s",temph); for(i=0;i<n;i++){a.h[i]=temph[i]-'0';mark2[a.h[i]]++;} if(mark2[2]<2||mark2[0]<1||mark2[1]<1){printf("-1\n");continue;} a.change(); mark[a.num]=true; a.count=0; Q.push(a); if(check(a)){printf("0\n");continue;} while(!ans) { a=Q.front();Q.pop();a.count++; for(i=1;i<n;i++)//i標記需要交換的數的後面那個位置 { temp=a; int tempi=temp.h[i];//交換這倆值 temp.h[i]=temp.h[i-1]; temp.h[i-1]=tempi; temp.change(); if(check(temp)==true){ans=temp.count;break;} if(mark[temp.num])continue; mark[temp.num]=true; Q.push(temp); } } printf("%d\n",ans); } return 0; }
