题目大意：略
每次选择一个最大深度K，跑IDA*
估价函数H=8-中间8个格里出现次数最多的数的个数x，即把它填满这个数最少需要8-x次操作，如果dep+H>K，就跳出..
深搜的时候暴力修改，记录操作的方向，回溯再改回来就行了，根本不用把网格压进状态里嘛..
又水了一篇博客
#include <queue> #include <cstdio> #include <cstring> #include <algorithm> #define NN 2010 #define ll long long #define uint unsigned int #define ull unsigned long long #define inf 0x3f3f3f3f using namespace std; int ans[NN]; int mp[20][20],tmp[10]; int xx[]={1,1,2,2,3,3,3,3,3,3,3,4,4,5,5,5,5,5,5,5,6,6,7,7}; int yy[]={3,5,3,5,1,2,3,4,5,6,7,3,5,1,2,3,4,5,6,7,3,5,3,5}; int sum[5],op[NN],num; int esti() { int x,y; sum[1]=sum[2]=sum[3]=0; x=xx[6],y=yy[6],sum[mp[x][y]]++; x=xx[7],y=yy[7],sum[mp[x][y]]++; x=xx[8],y=yy[8],sum[mp[x][y]]++; x=xx[11],y=yy[11],sum[mp[x][y]]++; x=xx[12],y=yy[12],sum[mp[x][y]]++; x=xx[15],y=yy[15],sum[mp[x][y]]++; x=xx[16],y=yy[16],sum[mp[x][y]]++; x=xx[17],y=yy[17],sum[mp[x][y]]++; return 8-max(sum[1],max(sum[2],sum[3])); } void A(){ for(int i=0;i<7;i++) mp[i][3]=mp[i+1][3]; mp[7][3]=mp[0][3],mp[0][3]=0; } void B(){ for(int i=0;i<7;i++) mp[i][5]=mp[i+1][5]; mp[7][5]=mp[0][5],mp[0][5]=0; } void C(){ for(int i=8;i>1;i--) mp[3][i]=mp[3][i-1]; mp[3][1]=mp[3][8],mp[3][8]=0; } void D(){ for(int i=8;i>1;i--) mp[5][i]=mp[5][i-1]; mp[5][1]=mp[5][8],mp[5][8]=0; } void E(){ for(int i=8;i>1;i--) mp[i][5]=mp[i-1][5]; mp[1][5]=mp[8][5],mp[8][5]=0; } void F(){ for(int i=8;i>1;i--) mp[i][3]=mp[i-1][3]; mp[1][3]=mp[8][3],mp[8][3]=0; } void G(){ for(int i=0;i<7;i++) mp[5][i]=mp[5][i+1]; mp[5][7]=mp[5][0],mp[5][0]=0; } void H(){ for(int i=0;i<7;i++) mp[3][i]=mp[3][i+1]; mp[3][7]=mp[3][0],mp[3][0]=0; } int dfs(int dep,int ma) { if(esti()==0) return mp[3][3]; if(dep>=ma) return 0; if(esti()>ma-dep) return 0; int ans; A();ans=dfs(dep+1,ma);F(); if(ans){op[++num]=1;return ans;} B();ans=dfs(dep+1,ma);E(); if(ans){op[++num]=2;return ans;} C();ans=dfs(dep+1,ma);H(); if(ans){op[++num]=3;return ans;} D();ans=dfs(dep+1,ma);G(); if(ans){op[++num]=4;return ans;} E();ans=dfs(dep+1,ma);B(); if(ans){op[++num]=5;return ans;} F();ans=dfs(dep+1,ma);A(); if(ans){op[++num]=6;return ans;} G();ans=dfs(dep+1,ma);D(); if(ans){op[++num]=7;return ans;} H();ans=dfs(dep+1,ma);C(); if(ans){op[++num]=8;return ans;} return 0; } int a[30]; int main() { //freopen("t2.in","r",stdin); while(scanf("%d",&a[0])&&a[0]!=0) { ull S=0;num=0; mp[xx[0]][yy[0]]=a[0]; for(int i=1;i<24;i++){ scanf("%d",&a[i]); mp[xx[i]][yy[i]]=a[i]; } int ans; ans=dfs(0,0); if(ans){ printf("No moves needed %d ",ans); continue; } for(int k=1;k<=500;k++){ ans=dfs(0,k); if(ans){ for(int i=num;i>=1;i--) printf("%c",op[i]+'A'-1); puts(""); printf("%d ",ans); break; } } } return 0; }