题意
4*2个格子分别为
1234 8765 的魔板有3种操作，A：上下两排互换，B：最后一列放到第一列前面，C：中间四个顺时针旋转1格。 现在给出目标状态，找出最少步数可从原始状态到达目标状态，且输出最小字典序的操作序列。题解
bfs，全排列编码判重可以用康托展开，也可以用vis[8][8][8][8][8][8][8]来判重，因为第八位是固定的，所以要开\(8^7\)的空间。
代码
/*USER:19flipp1TASK:msquareLANG:C++*/#include#include #include #include #define ll long long#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);#define N 10using namespace std;int a[N],fac[N];struct node{ int a[N]; int d; char s[25];}nd;bool vis[320000];int cantor(int a[N]){ int ans=0,c; for(int i=1;i<8;i++){ c=0; for(int j=i;j<=8;j++)if(a[i]>a[j])c++; ans+=fac[8-i]*c; } return ans;}void work(int a[],int i){ if(i==0){ for(int j=1;j<=4;j++)swap(a[j],a[9-j]); }else if(i==1){ int t=a[1]; a[1]=a[4],a[4]=a[3],a[3]=a[2],a[2]=t; t=a[5]; a[5]=a[6],a[6]=a[7],a[7]=a[8],a[8]=t; }else if(i==2){ int t=a[2]; a[2]=a[7];a[7]=a[6];a[6]=a[3];a[3]=t; }}void bfs(){ queue q; node p; for(int i=1;i<=8;i++)p.a[i]=i; p.d=0; q.push(p); while(!q.empty()){ node p=q.front(); q.pop(); int ok=1; for(int i=1;i<=8;i++)if(p.a[i]!=nd.a[i]){ok=0;break;} if(ok){ printf("%d\n",p.d); for(int i=1;i<=p.d;i++) printf("%c",p.s[i]); puts(""); break; } for(int i=0;i<3;i++){ node np=p; work(np.a,i); int num=cantor(np.a); if(!vis[num]){ vis[num]=1; np.d++; np.s[np.d]='A'+i; q.push(np); } } }}int main(){ in(msquare); fac[0]=1; for(int i=1;i<=8;i++){ scanf("%d",&nd.a[i]); fac[i]=fac[i-1]*i; } bfs(); return 0;}
代码2
/*USER:19flipp1TASK:msquareLANG:C++*/#include#include #include #include #define ll long long#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);#define N 10using namespace std;int a[N],fac[N];struct node{ int a[N]; int d; char s[25];}nd;bool vis[8][8][8][8][8][8][8];void work(int a[],int i){ if(i==0){ for(int j=1;j<=4;j++)swap(a[j],a[9-j]); }else if(i==1){ int t=a[1]; a[1]=a[4],a[4]=a[3],a[3]=a[2],a[2]=t; t=a[5]; a[5]=a[6],a[6]=a[7],a[7]=a[8],a[8]=t; }else if(i==2){ int t=a[2]; a[2]=a[7];a[7]=a[6];a[6]=a[3];a[3]=t; }}bool Vis(int a[]){ bool &t=vis[a[1]-1][a[2]-1][a[3]-1][a[4]-1][a[5]-1][a[6]-1][a[7]-1]; if(t)return 1; t=1; return 0;}void bfs(){ queue q; node p; for(int i=1;i<=8;i++)p.a[i]=i; p.d=0; q.push(p); while(!q.empty()){ node p=q.front(); q.pop(); int ok=1; for(int i=1;i<=8;i++)if(p.a[i]!=nd.a[i]){ok=0;break;} if(ok){ printf("%d\n",p.d); for(int i=1;i<=p.d;i++) printf("%c",p.s[i]); puts(""); break; } for(int i=0;i<3;i++){ node np=p; work(np.a,i); if(!Vis(np.a)){ np.d++; np.s[np.d]='A'+i; q.push(np); } } }}int main(){ in(msquare); fac[0]=1; for(int i=1;i<=8;i++){ scanf("%d",&nd.a[i]); fac[i]=fac[i-1]*i; } bfs(); return 0;}