背景 Background
话说上一回，晴天小猪不畏千难万险、千辛万苦、千磨万难……终于爬上了那座深山，来到了那位隐者的小屋中，但它不知道，有一个问题正等待着它……
晴天小猪一推开门，就发现那里……空无一人？但在屋中央有一个石桌，上面有一些字(强吧)，最大的几个：如要见我，先过了这道关再说！
晴天小猪定睛一看，终于发现桌上密密麻麻布满了字，费了九天二猪之力，终于将题目看完，大意是：为了维护世界的和平……我们需要让九位勇士组成一个3*3的阵型去屠龙，但是这个阵型的要求很奇特，要九个人按照强弱依次编号1~9，且阵型中每行、每列、每条长对角线上的数字和都为15，这样才能使龙对勇士和阵型收到的损害最小，但九位勇士光是争夺名次就开始翻脸，各位**(任君想象)忙得不可开交，但晴天小猪也急得不可开交(-_-|||)），只好向你求助。
描述 Description
现在假设九位勇士已编好了号(感觉好像有人盯着我……)并站好了位置，例如：
7 8 9
1 2 3
4 5 6
每一次交换都可以将相邻的两位勇士(也就是编号……)交换位置，例如：
7 9 8
1 2 3 (8与9交换)
4 5 6
或
7 8 9
4 2 3 (4与1交换)
1 5 6
但不能
7 8 9
5 2 3 (1与5交换)
4 1 6
求最少的交换次数，使得九位勇士能在最短的时间内(当然是他们争完后……)以最安全的阵型去屠龙。
P.S:由于不能预测未来，各位**设想了许多的阵型(-_-||)，所以给了你10组阵型(测试点)，每组50个……
输入格式 Input Format
输入数据一共3*50行，每个数据中用3*3的9个不同的1~9的数字表示初始状态。
(样例就只给几个阵型了^_^)
输出格式 Output Format
每行一个数，即对应的初始阵型到所需阵型所需最少的交换次数，如果无解，输出-1。
分析：
BFS+康托展开.
1.对于每个成功的状态我们先算出它的康托展开，对于后面的BFS时就只需check是否是那些符合的状态即可，时间上快了很多。
2.对于那些搜索过的状态用个bool数组标记一下，费事再去搜索浪费时间。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int hashnum[8]={69075,77577,135290,157121,
205760,227591,285304,293806};
const int F[10]={0,1,2,6,24,120,720,5040,40320,362880};
struct node
{
int a[10],dep;
} list[400000];
int hash[362890];
void Swap(int &x,int &y)
{
int t=x; x=y; y=t;
}
int kangtuo(int *a)
{
int k,num,s; bool bk[10];
memset(bk,false,sizeof(bk));
s=1; k=8;
for (int i=1;i<=9;i++,k--)
{
num=0;
bk[a[i]]=true;
for (int j=1;j<=a[i]-1;j++)
if (!bk[j]) num++;
s+=num*F[k];
}
return s;
}
void bfs()
{
int head,tail,k;
head=tail=1; list[1].dep=0;
while (head<=tail)
{
for (int i=1;i<=3;i++)
for (int j=1;j<=2;j++)
{
tail++;
list[tail]=list[head];
list[tail].dep++;
Swap(list[tail].a[(i-1)*3+j],list[tail].a[(i-1)*3+j+1]);
k=kangtuo(list[tail].a);
if (hash[k]==2)
{
printf("%d\n",list[tail].dep);
return ;
}
if (hash[k]==1) tail--;
hash[k]=1;
}
for (int i=1;i<=2;i++)
for (int j=1;j<=3;j++)
{
tail++;
list[tail]=list[head];
list[tail].dep++;
Swap(list[tail].a[(i-1)*3+j],list[tail].a[i*3+j]);
k=kangtuo(list[tail].a);
if (hash[k]==2)
{
printf("%d\n",list[tail].dep);
return ;
}
if (hash[k]==1) tail--;
hash[k]=1;
}
head++;
}
printf("-1\n");
}
int main()
{
for (int i=1;i<=50;i++)
{
for (int i=1;i<=362880;i++) hash[i]=0;
for (int i=0;i<=7;i++) hash[hashnum[i]]=2;
for (int i=1;i<=9;i++) scanf("%d",&list[1].a[i]);
int k=kangtuo(list[1].a);
if (hash[k]==2)
{
printf("0\n");
continue;
}
bfs();
}
return 0;
}