Description
给定1到N的一个排列，再给定一些允许的交换方法，要求用最少的交换次数把该排列变为1，2，3，，，N。 Input
第一行包含两个整数N(1<=N<=12)和M(1<=M<=N*(N-1)/2),表示序列的长度以及允许的交换方案。 第二行输入1到N个初始排列情况。 接下来M行，每行两个整数A和B描述一个允许的交换方案,表示允许把当前排列中的第A个数和第B个数进行交换，保证A和B不相同。 输入保证一定存在解。 Output
输出一个整数表示最少需要的交换次数。
思路：
双向bfs。 两边搜，搜到两边都可以搜到的点，就直接输出。
代码：
#include<cstdio> #include<memory.h> #include<iostream> #define mo 1000007 using namespace std; long long p[mo],k[3*mo],k2[3*mo],jz[15],kp; bool bz[mo]; int temp[mo],a[15],b[15],f[15],x[150][2]; int n,m,l,o,t; int hash(long long x) { int w=x%mo; while (p[w]&&p[w]!=x) w=(w+1)%mo; return w; } long long zhuan() { long long sum=0; for (int i=1;i<=n;i++) sum+=b[i]*jz[n-i]; return sum; } void feng(long long x) { for (int i=1;i<=n;i++) { f[i]=x/jz[n-i]; x=x%jz[n-i]; } } int main() { jz[0]=1; for (int i=1;i<=13;i++) jz[i]=jz[i-1]*12; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=i-1;a[i]--; } for (int i=1;i<=m;i++) scanf("%d%d",&x[i][0],&x[i][1]); k[1]=zhuan();l=hash(k[1]);p[l]=k[1];bz[l]=1; memcpy(b,a,sizeof(b)); k2[1]=zhuan();l=hash(k2[1]);p[l]=k2[1]; if (k[1]==k2[1]) { printf("0"); return 0; } int head=0,tail=1,head1=0,tail1=1; while (head<tail&&head1<tail1) { head++; feng(k2[head]); o=temp[hash(k2[head])]; for (int i=1;i<=m;i++) { memcpy(b,f,sizeof(b)); t=b[x[i][0]]; b[x[i][0]]=b[x[i][1]]; b[x[i][1]]=t; kp=zhuan(); l=hash(kp); if (p[l]==kp) { if (bz[l]) { printf("%d",temp[l]+o+1); return 0; } } else { tail++; k2[tail]=kp; p[l]=kp; bz[l]=0; temp[l]=o+1; } } head1++; feng(k[head1]); o=temp[hash(k[head1])]; for (int i=1;i<=m;i++) { memcpy(b,f,sizeof(b)); t=b[x[i][0]]; b[x[i][0]]=b[x[i][1]]; b[x[i][1]]=t; kp=zhuan(); l=hash(kp); if (p[l]==kp) { if (!bz[l]) { printf("%d",temp[l]+o+1); return 0; } } else { tail1++; k[tail1]=kp; p[l]=kp; bz[l]=1; temp[l]=o+1; } } } }