每次移动空位而不是骑士
设当前搜到第步，剩下个骑士未回到位置
若，则返回跑得飞快
其实还可以加点什么小剪枝
若当前和交换，则下次不换回去
既然直接搜能过（实现起来有点小烦），就没加这个剪枝1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
const int n=5,N=6;
const int dx[]={1,-1,1,-1,2,-2,2,-2};
const int dy[]={2,2,-2,-2,1,1,-1,-1};
const int to[N][N]={{'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'}};
int dep,w[N][N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') {t=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*t;
}
inline char get()
{
register char ch=getchar();
while (ch!='1'&&ch!='0'&&ch!='*') ch=getchar();
return ch;
}
bool dfs(int k,int xx,int yy,int num)
{
if (k+num>dep) return 0;
if (!num) return 1;
for(int i=0;i<8;i++)
{
int x=xx+dx[i],y=yy+dy[i];
if (x>0&&x<=n&&y>0&&y<=n)
{
int nxt=num;
nxt+=w[x][y]==to[x][y];
nxt-=w[x][y]==to[xx][yy];
swap(w[x][y],w[xx][yy]);
if (dfs(k+1,x,y,nxt)) return 1;
swap(w[x][y],w[xx][yy]);
}
}
return 0;
}
int main()
{
int T=read();
while (T--)
{
int num=0,f=0,xx,yy;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
w[i][j]=get();
if (to[i][j]!=w[i][j]&&w[i][j]!='*') num++;
if (w[i][j]=='*') xx=i,yy=j;
}
for(dep=num;dep<=15&&!f;dep++)
if (dfs(0,xx,yy,num))
f=1,printf("%d\n",dep);
if (!f) puts("-1");
}
return 0;
}