给出如下图形，其中23个格子填有1~23，移动规则与八数码相同，给定始终态，问是否可达。
首先八个角的数字是不可能移动出去的，所以先对八个角进行判断，如果为空格则和附近格子的数进行交换，问题转化为16数码问题。和八数码类似，可以用奇偶性来判断两个状态是否可达，不同的是，将一个数上下移动会影响的整体的奇偶性，一个很好的方法就是"弓"字行统计，这样移动后奇偶性就不会改变了。
#include <stdio.h> #include <string.h> int cas,a[25],b[25]; //八个顶点必须相同,若为0和相邻的置换 int p1[]={0,1,2,7,16,21,22,23, 3,6,3,6,17,20,17,20}; //蛇形统计,避免要讨论奇偶性的情况 int p2[]={3,4,5,6,11,10,9,8,12,13,14,15,20,19,18,17}; void swap(int &a,int &b){a^=b,b=a^b,a=a^b;} int main(){ //freopen("test.in","r",stdin); scanf("%d",&cas); while(cas--){ for(int i=0;i<24;i++)scanf("%d",&a[i]); for(int i=0;i<24;i++)scanf("%d",&b[i]); for(int i=0;i<8;i++){ if(a[p1[i]]==0)swap(a[p1[i]],a[p1[i+8]]); if(b[p1[i]]==0)swap(b[p1[i]],b[p1[i+8]]); } int ans=1,nxa=0,nxb=0; for(int i=0;i<8;i++) if(a[p1[i]]!=b[p1[i]])ans=0; if(!ans){printf("Y\n");continue;} for(int i=0;i<16;i++){ for(int j=i+1;j<16;j++){ if(a[p2[i]]&&a[p2[j]]>a[p2[i]])nxa++; if(b[p2[i]]&&b[p2[j]]>b[p2[i]])nxb++; } } if((nxa-nxb)&1)printf("Y\n"); else printf("N\n"); } return 0; }