考虑 $IDA*$ 算法。

每次枚举递推的深度，设计估价函数$g(n)$。因为在最好情况下，即使每一步都做出了贡献，它最多也只能使得目前图形与目标图形差异数减少 1 ，所以我们不妨就定义 $g(n)$ 等于目前图形与目标图形的差异数，然后正常 $IDA*$ 即可。

为理解方便，提供一个因为常数较大而只有 $90 pts$ 的代码，仅供参考。实现时注意常数问题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class WC{
    public:
    const ll noip;
    private:
};
struct Node{
    ll posx,posy;
};
Node d;
ll T;
ll maxinumdepth=15;
ll randw(){
    srand((unsigned)time(0));
    return 1000;
}
#define INF randw()
#define acc(x,y) (x>=1&&x<=5&&y>=1&&y<=5)?true:false
#define FOR(x,y,k) for(ll i=x;i<=y;i+=k)
#define N 8
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
ll givenmap[N][N];
ll preans=INF;
ll goalmap[N][N]={{0,0,0,0,0,0},{0,1,1,1,1,1},{0,2,1,1,1,1},{0,2,2,3,1,1},{0,2,2,2,2,1},{0,2,2,2,2,2}};
void print(){
    for(ll i=1;i<=5;i++,cout<<endl){
        for(ll j=1;j<=5;j++) cout<<givenmap[i][j];
    }
} 
bool check(){
    for(ll i=1;i<=5;i++)
    for(ll j=1;j<=5;j++)
    {
        if(goalmap[i][j]^givenmap[i][j]) return false;
    }
    return true;
}
ll superior(){
    ll ans=0;
    for(ll i=1;i<=5;++i)
    for(ll j=1;j<=5;++j)
    if(goalmap[i][j]^givenmap[i][j]) ++ans;
    return ans;
}
void IDA(Node u,ll num,ll maxd){
//  cout<<u.posx<<' '<<u.posy<<endl;
    if(check()) {
        preans=min(preans,num);
        //goto ZAG;
        return ;
    }
    for(ll i=1;i<=8;i++){
        ll fx=dx[i]+u.posx;
        ll fy=dy[i]+u.posy;
        if(acc(fx,fy)){
            swap(givenmap[u.posx][u.posy],givenmap[fx][fy]);
    //      ++num;
            Node p;
            p.posx=fx,p.posy=fy;
            if(num+superior()<maxd)IDA(p,num+1,maxd);
//          --num;
            swap(givenmap[u.posx][u.posy],givenmap[fx][fy]);            
        }
    }
    return ;
}
signed main(){
//  print();
    cin>>T;
    FOR(1,T,1){
        preans=INF;
        for(ll i=1;i<=5;i++)
        for(ll j=1;j<=5;j++)
        {
            char dig;
            cin>>dig;
            if(isdigit(dig)) 
            {
                ll digs=ll(dig)-48;
                givenmap[i][j]=(digs^1)?(digs+2):digs;
            }
            else{
                givenmap[i][j]=3;
                d.posx=i;
                d.posy=j;
            }
        }
        if(check()) {cout<<0<<endl; goto Zag;}
//      print();
        for(ll i=0;i<=maxinumdepth+1;++i){
            ll maxd=i;
            IDA(d,0,maxd);
            if(preans^INF) {
            printf("%d\n",preans);
            goto Zag;}
        }
        printf("%d\n",-1);
        Zag:;
    }
    exit(0);
}