1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,ans,stx,sty,T;13 bool pd;14 char s[10][10];15 char aim[8][8]={"000000","011111","001111","000*11","000001","000000"}; 16 llg p[8][2]={{1,2},{-1,2},{-1,-2},{1,-2},{-2,-1},{-2,1},{2,-1},{2,1}};  17 18 llg cal()19 {20     llg sum=0;21     for (llg i=1;i<=5;i++) 22         for (llg j=1;j<=5;j++)23             if (s[i][j]!=aim[i][j]) sum++;24     return sum;25 }26 27 void ss(llg cs,llg x,llg y)28 {29     if (cs>ans || pd) return ;30     llg val=cal();31     if (val==0) {pd=1; return ;}32     if (cs>ans) return ;33     if (cs+val-1>ans) return ;34     for (llg i=0;i<8;i++)35     {36         llg nx=x+p[i][0],ny=y+p[i][1];37         if (nx<1 || ny<1 || nx>5 || ny>5) continue;38         swap(s[x][y],s[nx][ny]);39         ss(cs+1,nx,ny);40         swap(s[x][y],s[nx][ny]);41     }42 }43 44 int main()45 {46     yyj("bzoj1085");47     cin>>T;48     while (T--)49     {50         for (llg i=1;i<=5;i++) cin>>(s[i]+1);51         for (llg i=1;i<=5;i++)52             for (llg j=1;j<=5;j++)53                 if (s[i][j]==‘*‘)54                     stx=i,sty=j;55         for (ans=0;ans<=15;ans++)56         {57             pd=0;58             ss(0,stx,sty);59             if (pd) break;60         }61         if (ans==16) ans=-1;62         cout<<ans<<endl;63     }64     return 0;65 }