本地预处理跑n!组用时2.2s……交上去就T
难道这个题真的有毒？
附上测速版的代码 写得异常的丑
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<time.h>
using namespace std;
struct node
{
int mat[10];
int cantor,step;
};
inline int jie(int num)
{
int tot=1;
for(int i=1;i<=num;i++)tot*=i;
return tot;
}
int hashtable[10000000];
void getcantor(node &a)
{
a.cantor=0;
int tot=0;
int cou=0;
for(int i=1;i<=9;i++)
{
cou=0;
for(int j=i+1;j<=9;j++)
{
if(a.mat[i]>a.mat[j])
{
cou++;
}
}
a.cantor+=cou*jie(9-i);
}
a.cantor++;
}
queue<node> q;
void bfs()
{
node tmp,now,o;
now.mat[1]=4,now.mat[2]=9,now.mat[3]=2,now.mat[4]=3,
now.mat[5]=5,now.mat[6]=7,now.mat[7]=8,now.mat[8]=1;now.mat[9]=6;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=2,now.mat[2]=9,now.mat[3]=4,now.mat[4]=7,
now.mat[5]=5,now.mat[6]=3,now.mat[7]=6,now.mat[8]=1;now.mat[9]=8;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=8,now.mat[2]=1,now.mat[3]=6,now.mat[4]=3,
now.mat[5]=5,now.mat[6]=7,now.mat[7]=4,now.mat[8]=9;now.mat[9]=2;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=6,now.mat[2]=7,now.mat[3]=2,now.mat[4]=1,
now.mat[5]=5,now.mat[6]=9,now.mat[7]=8,now.mat[8]=3;now.mat[9]=4;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=8,now.mat[2]=3,now.mat[3]=4,now.mat[4]=1,
now.mat[5]=5,now.mat[6]=9,now.mat[7]=6,now.mat[8]=7;now.mat[9]=2;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=2,now.mat[2]=7,now.mat[3]=6,now.mat[4]=9,
now.mat[5]=5,now.mat[6]=1,now.mat[7]=4,now.mat[8]=3;now.mat[9]=8;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=2,now.mat[2]=7,now.mat[3]=6,now.mat[4]=9,
now.mat[5]=5,now.mat[6]=1,now.mat[7]=4,now.mat[8]=3;now.mat[9]=8;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=4,now.mat[2]=3,now.mat[3]=8,now.mat[4]=9,
now.mat[5]=5,now.mat[6]=1,now.mat[7]=2,now.mat[8]=7;now.mat[9]=6;
getcantor(now);
now.step=0;
q.push(now);
now.mat[1]=6,now.mat[2]=1,now.mat[3]=8,now.mat[4]=7,
now.mat[5]=5,now.mat[6]=3,now.mat[7]=2,now.mat[8]=9;now.mat[9]=4;
getcantor(now);
now.step=0;
q.push(now);
while(!q.empty())
{
now=q.front();q.pop();
if(hashtable[now.cantor]!=-1)continue;
hashtable[now.cantor]=now.step;
o=now;
swap(o.mat[2],o.mat[1]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[2],o.mat[3]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[2],o.mat[5]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[4],o.mat[1]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[4],o.mat[5]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[4],o.mat[7]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[6],o.mat[5]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[6],o.mat[3]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[6],o.mat[9]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[8],o.mat[7]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[8],o.mat[9]);
getcantor(o);
o.step++;q.push(o);
o=now;
swap(o.mat[8],o.mat[5]);
getcantor(o);
o.step++;q.push(o);
}
}
int main()
{
clock_t begin,end;
begin=clock();
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
memset(hashtable,-1,sizeof(hashtable));
node tmp;
bfs();
while(scanf("%d",&tmp.mat[1])!=EOF)
{
for(int i=2;i<=9;i++)
{
scanf("%d",&tmp.mat[i]);
}
getcantor(tmp);
printf("%d\n",hashtable[tmp.cantor]);
}
end=clock();
printf("%.4f",(double)(end-begin)/CLOCKS_PER_SEC);
return 0;
}