只有9!=362880个状态，用康托展开hash一下直接bfs即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000005,fac[]={1,1,2,6,24,120,720,5040,40320,362880},d1[]={4,1,2,7,5,3,8,9,6},d2[]={1,2,3,6,4,5,7,8,9};
int a[15],b[15],v[15],dis[N],la[N],tot;
long long s,t=123456789,ans[N];
int has(long long x)
{
for(int i=9;i>=1;i--)
a[i]=x%10,x/=10;
int r=0;
for(int i=1,sm;i<=9;i++)
{
sm=0;
for(int j=i+1;j<=9;j++)
if(a[j]<a[i])
sm++;
r+=fac[9-i]*sm;
}
return r;
}
long long rel(int x)
{
memset(v,0,sizeof(v));
long long r=0;
for(int i=9;i>=1;i--)
{
int t=x/fac[i-1];
x%=fac[i-1];
for(int j=1,w=0;j<=9;j++)
if(!v[j])
{
w++;
if(w==t+1)
{
r=r*10+j;
v[j]=1;
break;
}
}
}
return r;
}
int main()
{
for(int i=1,x;i<=9;i++)
scanf("%d",&x),s=s*10+x+1;
s=has(s),t=has(t);//cerr<<s<<" "<<t<<" "<<rel(s)<<" "<<rel(t)<<endl;
queue<int>q;
dis[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();//cerr<<u<<endl<<rel(u)<<endl;
q.pop();
if(u==t)
break;
long long x=rel(u),v1=0,v2=0;
for(int i=9;i>=1;i--)
a[i]=x%10,x/=10;
for(int i=0;i<9;i++)
v1=v1*10+a[d1[i]],v2=v2*10+a[d2[i]];//cerr<<v1<<" "<<v2<<endl;
v1=has(v1),v2=has(v2);//cerr<<v1<<" "<<v2<<endl;
if(!dis[v1])
la[v1]=u,dis[v1]=dis[u]+1,q.push(v1);
if(!dis[v2])
la[v2]=u,dis[v2]=dis[u]+1,q.push(v2);
}
if(!dis[t])
{
puts("UNSOLVABLE");
return 0;
}
printf("%d
",dis[t]-1);
for(int i=t;i!=s;i=la[i])
ans[++tot]=rel(i);
ans[++tot]=rel(s);
for(int i=tot;i>=1;i--)
{
for(int j=1;j<=9;j++)
a[j]=ans[i]%10-1,ans[i]/=10;
printf("%d %d %d
%d %d %d
%d %d %d
",a[9],a[8],a[7],a[6],a[5],a[4],a[3],a[2],a[1]);
}
return 0;
}