```cpp
#include "bits/stdc++.h"
using namespace std;
char a[10][10];
char r[10][10]=
{
"",
" 11111",
" 01111",
" 00*11",
" 00001",
" 00000",
};
int dep,t,s1,s2;
int fx[]={0,-1,-2,-2,-1,1,2,2,1};
int fy[]={0,-2,-1,1,2,2,1,-1,-2};
int f()
{
int res=0;
for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) res+=(a[i][j]!=r[i][j]);
return res;
}
bool dfs(int x,int y,int step)
{
if(step==dep) return f()==0;
for(int i=1;i<=8;i++)
{
int tx=x+fx[i],ty=y+fy[i];
if(tx>=1&&tx<=5&&ty>=1&&ty<=5)
{
swap(a[tx][ty],a[x][y]);
if(step+f()<=dep) if(dfs(tx,ty,step+1)) return true;
swap(a[tx][ty],a[x][y]);
}
}
return false;
}
signed main(void)
{
cin>>t;
while(t--)
{
for(int i=1;i<=5;i++)
{
for(int j=1;j<=5;j++)
{
cin>>a[i][j];
if(a[i][j]=='*') s1=i,s2=j;
}
}
bool f=false;
for(dep=0;dep<=15;dep++)
{
if(dfs(s1,s2,0))
{
cout<<dep<<endl;
f=true;
break;
}
}
if(f==false) cout<<"-1\n";
}
return 0;
}
by zhangjunxian1234 @ 2023-09-23 18:52:43