[cpp] 描述：坑人的一道題，不過也不難，就是數字交換，只有一正一負的數字才存在交換，並且交換之後不能形成素數 #include <cstdio> #include <cstdlib> #include <cstring> #define N 1000003 int t[10]= {1,2,3,4,5,6,7,8},cmp[]= {4,6,8,9,10,12,14,15}; int head[N],next[N],count[N]; int str[N][10][2]; int m=1,sum,flag; int hash(int (*p)[2]) { int x=0; for(int i=0; i<8; i++) x=(x*10+p[i][0])%N; return x; } bool insert(int x,int rear) { int c=head[x]; while(c!=-1) { int z=0; for(int i=0; i<8; i++) if(str[rear][i][0]!=str[c][i][0]) { z=1; break; } if(z) c=next[c]; else return false; } next[rear]=head[x]; head[x]=rear; return true; } void bfs() { memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); memset(count,0,sizeof(count)); flag=0; int rear=1,front=0; while(front<rear&&rear<N) { for(int i=0; i<8; i++) for(int j=0; j<8; j++) if(str[front][j][1]+str[front][i][1]==1) { int c=0; for(int k=0; k<8; k++) if(str[front][i][0]+str[front][j][0]==cmp[k]) { c=-1; break; } if(c!=-1)//前插 { if(j>i) { for(int k=0; k<i; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=j; k<8; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i; k<j-1; k++) { str[rear][k][0]=str[front][k+1][0]; str[rear][k][1]=str[front][k+1][1]; } str[rear][j-1][0]=str[front][i][0]; str[rear][j-1][1]=str[front][i][1]; } else { for(int k=0; k<j; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i+1; k<8; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i; k>j; k--) { str[rear][k][0]=str[front][k-1][0]; str[rear][k][1]=str[front][k-1][1]; } str[rear][j][0]=str[front][i][0]; str[rear][j][1]=str[front][i][1]; } for(int k=0; k<8; k++) if(str[rear][k][0]!=t[k]) { flag=1; break; } if(!flag) { sum=count[front]+1; return; } else { flag=0; int x=hash(str[rear]); if(insert(x,rear)) { count[rear]=count[front]+1; rear++; } } } if(c!=-1)//後插 { if(j>i) { for(int k=0; k<i; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=j+1; k<8; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i; k<j; k++) { str[rear][k][0]=str[front][k+1][0]; str[rear][k][1]=str[front][k+1][1]; } str[rear][j][0]=str[front][i][0]; str[rear][j][1]=str[front][i][1]; } else { for(int k=0; k<=j; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i+1; k<8; k++) { str[rear][k][0]=str[front][k][0]; str[rear][k][1]=str[front][k][1]; } for(int k=i; k>j+1; k--) { str[rear][k][0]=str[front][k-1][0]; str[rear][k][1]=str[front][k-1][1]; } str[rear][j+1][0]=str[front][i][0]; str[rear][j+1][1]=str[front][i][1]; } for(int k=0; k<8; k++) if(str[rear][k][0]!=t[k]) { flag=1; break; } if(!flag) { sum=count[front]+1; return; } else { flag=0; int x=hash(str[rear]); if(insert(x,rear)) { count[rear]=count[front]+1; rear++; } } } } front++; } } int main() { // freopen("a.txt","r",stdin); while(scanf("%d",&str[0][0][0])!=EOF) { if(!str[0][0][0]) break; flag=0; sum=-1; if(str[0][0][0]>0) str[0][0][1]=1; else { str[0][0][1]=0; str[0][0][0]=-str[0][0][0]; } for(int i=1; i<8; i++) { scanf("%d",&str[0][i][0]); if(str[0][i][0]>0) str[0][i][1]=1; else { str[0][i][1]=0; str[0][i][0]=-str[0][i][0]; } } www.2cto.com for(int i=0; i<8; i++) if(str[0][i][0]!=t[i]) { flag=1; break; } if(flag) { bfs(); printf("Case %d: %d\n",m++,sum); } else printf("Case %d: 0\n",m++); } return 0; }
