记录：https://www.luogu.com.cn/record/197943083

代码：

#include<bits/stdc++.h>
using namespace std;
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
const char Tmp[10][10]={
        {0,0,0,0,0,0},
        {0,'1','1','1','1','1'},
        {0,'0','1','1','1','1'},
        {0,'0','0','*','1','1'},
        {0,'0','0','0','0','1'},
        {0,'0','0','0','0','0'}
};
char mp[6][6];
int g() {
    int res=0;
    for(int i=1;i<=5;i++) {
        for(int j=1;j<=5;j++) {
            if(mp[i][j]!=Tmp[i][j]) {
                res++;
            }
        }
    }
    return res;
}
int f(int cnt) {
    return cnt+g();
}
bool ans;
void IDAstar(int x,int y,int cnt,int maxdep) {
    if(cnt==maxdep) {
        if(!g()) {
            ans=true;
        }
        return ;
    }
    for(int i=0;i<8;i++) {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(!(nx<1||nx>5||ny<1||ny>5)) {
            swap(mp[x][y],mp[nx][ny]);
            if(f(cnt)<=maxdep) {
                IDAstar(nx,ny,cnt+1,maxdep);
            }
            swap(mp[x][y],mp[nx][ny]);
        }
    }
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        ans=false;
        memset(mp,0,sizeof(mp));
        int sx,sy;
        for(int i=1;i<=5;i++) {
            for(int j=1;j<=5;j++) {
                cin>>mp[i][j];
                if(mp[i][j]=='*') {
                    sx=i,sy=j;
                }
            }
        }
        if(!g()) {
            cout<<0<<endl;
            goto tg;
        }
        for(int i=1;i<=15;i++) {
            IDAstar(sx,sy,0,i);
            if(ans) {
                cout<<i<<endl;
                goto tg;
            }
        }
        cout<<-1<<endl;
        tg:;
    }
    return 0;
}