这题和八数码十分相似，或许是我的遗留问题吧....敲完总是不过，各种错误。迟迟下不了手的原因就在于对空间的把握问题。要节约空间就必须设计一个好的hash函数,不然时空开销大。关键在于哈希怎么弄了？八位数--->87654321如果采用这么大的空间，空间消耗太大，许多内存都没采用，不行...
后来查了下资料，发现有康托展开恰好是结果全排列的哈希问题。有了康托展开之后，全排列的问题就可以采用最小的空间消耗了，8！=40320<<87654321;这样就可以用bfs了。
当然8个数也可以用8*3bit来表示。这样面向字节流的操作很快，而且空间更省。
根据百度百科理解的康托展开：
int cantor( int num )
{int ret=0;bool h[9]={false};for( int i=8;i>=2;i-- ){int k,t,b=1;t=num;while( t/10>0 ){k=t/10;t/=10;b*=10;}h[k]=true;num-=t*b;int p=0;for( int j=1;j<k;j++ )if( h[j]==false )p++;ret+=p*fec[i-1];}//printf( "ret:%d\n",ret );return ret;
}康托展开什么意思呢？
就是当前的最左端的数，比其小的未用的数的个数，这些最小的数作为最左端的数，余下的数再进行全排列（只要看余下的位数，与可用的数的个数就可以了），比如54321，最左端是5，那么比他小的，最左端可以放4,3,2,1,都是未被使用过且小的。如果放下4，则剩下4个空填放1,2,3,5,种类数4!所以为4*4!;那么余下的4321，比他小的呢？这里就用到了递归，小化同样的情况。最终得出解。
理解了康托展开之后，逆康托展开也很方便了。
Code：
/*
ID:sevenst4
LANG:C++
PROG:msquare
*/
#include<stdio.h>
#include<cstdlib>
using namespace std;struct node
{int square[8];char select;
}S,E;int fec[10]={ 1,1,2,6,24,120,720,5040,40320 };
int hash[8]={1,2,3,4,8,7,6,5};bool flag[50000]={false};
node queue[50000];
int pre[50000];int nodeToNum( node a )
{int ret=0;for( int i=0;i<8;i++ )ret=ret*10+a.square[hash[i]-1];return ret;
}int cantor( int num )
{int ret=0;bool h[9]={false};for( int i=8;i>=2;i-- ){int k,t,b=1;t=num;while( t/10>0 ){k=t/10;t/=10;b*=10;}h[k]=true;num-=t*b;int p=0;for( int j=1;j<k;j++ )if( h[j]==false )p++;ret+=p*fec[i-1];}//printf( "ret:%d\n",ret );return ret;
}void init()
{for( int i=0;i<8;i++ ){S.square[i]=hash[i];scanf( "%d",&E.square[hash[i]-1] );}
}void print( node t,int foot )
{char r[100];int step=0;for( int i=foot;pre[i]!=-1;i=pre[i] )r[step++]=queue[i].select;printf( "%d\n",step );int s=0;for( int i=step-1;i>=0;i-- ){s++;if( s%60==0 )printf( "\n" );printf( "%c",r[i] );}if( s%60!=0 )printf( "\n" );
}node rotate( node a,int n )
{if( n==1 ){for( int i=0;i<4;i++ ){int t=a.square[i];a.square[i]=a.square[i+4];a.square[i+4]=t;}}else if( n==2 ){int t1=a.square[3];int t2=a.square[7];for( int i=3;i>=0;i-- ){a.square[i]=a.square[i-1];a.square[i+4]=a.square[i+3];}a.square[0]=t1;a.square[4]=t2;}else if( n==3 ){int t=a.square[1];a.square[1]=a.square[5];a.square[5]=a.square[6];a.square[6]=a.square[2];a.square[2]=t;}return a;
}void bfs()
{int head=0,foot=1;queue[head]=S;if( nodeToNum(S)==nodeToNum(E) ){printf( "0\n\n" );return ;}flag[cantor(nodeToNum(S))]=true;int step=-1;pre[0]=-1;while( head!=foot ){node cur=queue[head];for( int i=1;i<=3;i++ ){node temp=rotate( cur,i );temp.select=i+'A'-1;int getnum=cantor(nodeToNum(temp));if( flag[getnum]==false ){flag[getnum]=true;pre[foot]=head;queue[foot++]=temp;}if( nodeToNum(temp)==nodeToNum(E) ){ print( temp,foot-1 );return ;}}head++;}
}int main()
{freopen( "msquare.in","r",stdin );freopen( "msquare.out","w",stdout );init();bfs();return 0;
}