1. 题目

传送门=￣ω￣=

2. 题解

就是个八数码问题，改了一下变换方式而已。同样是 bfs+哈希记录状态。
哈希方法就是把数码的每一个格子里面的数字作为哈希值的每一位数字
哈希可以康托展开，这样就直接用数组哈希就行了。
我是直接用 pb_ds 哈希，直接水过。

代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
typedef int st[3][3];
gp_hash_table<int,int> pre;
gp_hash_table<int,int> tot;
queue<int> que;
void stoi(int&tar,st a)
{
    tar=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)tar=tar*10+a[i][j];
}
void itos(st&tar,int a)
{
    memset(tar,0,sizeof(tar));
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)tar[i][j]=a%10,a/=10;
}
void midt(st&a){swap(a[1][1],a[1][2]),swap(a[1][0],a[1][1]);}
stack<int> sta;
void dfs(int a)
{
    if(!a)return;
    dfs(pre[a]);
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)sta.push(a%10),a/=10;
    for(int i=0;i<3;i++,putchar('\n'))
        for(int j=0;j<3;j++)printf("%d ",sta.top()),sta.pop();
    putchar('\n');
}
st beg;
int main()
{
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&beg[i][j]);
    int stb;
    stoi(stb,beg);
    que.push(stb),pre[stb]=0,tot[stb]=0;
    while(!que.empty())
    {
        int f=que.front();que.pop();
        st k;itos(k,f);
        midt(k);
        int p;stoi(p,k);
        if(!pre[p]&&p!=stb)que.push(p),pre[p]=f,tot[p]=tot[f]+1;
        midt(k),midt(k);
        int tem=k[0][0];
        k[0][0]=k[1][0],k[1][0]=k[2][0],k[2][0]=k[2][1],k[2][1]=k[2][2];
        k[2][2]=k[1][2],k[1][2]=k[0][2],k[0][2]=k[0][1],k[0][1]=tem;
        if(stoi(p,k),!pre[p]&&p!=stb)que.push(p),pre[p]=f,tot[p]=tot[f]+1;
    }
    if(!pre[12345678]&&12345678!=stb)puts("UNSOLVABLE"),exit(0);
    printf("%d\n",tot[12345678]),dfs(12345678);
    return 0;
}