[BZOJ1085][SCOI2005]骑士精神

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ███━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }int T,a[6][6],dx[]={1,2,2,1,-1,-2,-2,-1},dy[]={2,1,-1,-2,-2,-1,1,2},ff,b[6][6],x,y;const int S[6][6]={{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1},{0,0,0,0,0,1},{0,0,0,0,0,0}};
12 char chr;
13 inline int check(){int ans=0;
14     for(int i=1;i<=5;i++)
15         for(int j=1;j<=5;j++)
16             if(a[i][j]!=S[i][j]) ++ans;
17     return ans;
18 }void dfs(int stp,int x,int y,int depth){
19     if(stp==depth){if(!check()) ff=1;return;}
20     if(check()+stp>depth+1) return;
21     for(int i=0;i<8;i++){
22         int fx=x+dx[i],fy=y+dy[i];
23         if(fx<1||fy<1||fx>5||fy>5) continue;
24         swap(a[x][y],a[fx][fy]),dfs(stp+1,fx,fy,depth),swap(a[x][y],a[fx][fy]);
25     }
26 }int main(){
27     T=read();
28     while(ff=0,T--){
29         for(int i=1;i<=5;i++)
30             for(int j=1;j<=5;j++)
31                 cin>>chr,((chr=='*')?(x=i,y=j,b[i][j]=2):b[i][j]=chr-48);
32         for(int stp=1;stp<=15;stp++){
33             memcpy(a,b,sizeof(a));
34             dfs(0,x,y,stp);
35             if(ff){printf("%d\n",stp);break;}
36         }if(!ff) puts("-1");
37     }
38     return 0;
39 }
40 /**
41 *　　┏┓　　　┏┓+ +
42 *　┏┛┻━━━┛┻┓ + +
43 *　┃　　　　　　　┃
44 *　┃　　　━　　　┃ ++ + + +
45 *  ███━████+
46 *  ◥██◤　◥██◤ +
47 *　┃　　　┻　　　┃
48 *　┃　　　　　　　┃ + +
49 *　┗━┓　　　┏━┛
50 *　　　┃　　　┃ + + + +Code is far away from 　
51 *　　　┃　　　┃ + bug with the animal protecting
52 *　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
53 *　　　┃ 　　　　　　 ┣┓
54 *　　  ┃ 　　　　　 　┏┛
55 *　    ┗┓┓┏━┳┓┏┛ + + + +
56 *　　　　┃┫┫　┃┫┫
57 *　　　　┗┻┛　┗┻┛+ + + +
58 */