题目描述
在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。
在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。
给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。

输入格式
第一行有一个正整数T(T<=10)，表示一共有T组数据。

接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。

两组数据之间没有空行。

输出格式
每组数据输出占一行。

如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

输入样例：
2
10110
0111
10111
01001
00000
01011
1101
01110
输出样例：
7
-1
以前写的一道搜索题目；其实当时对astar的理解不是特别深刻，其实我们明白他只是一种形式，剪枝方法；
具体实现方法不过是当前实际情况加上估价函数的值决定下次取值的情况；
其实在这个题目中，我们要考虑到使用迭代加深，不明白的同学可以写一下加成序列仔细体会一下；
我们发现对于这样一个棋盘，我们最多移动15次吧，对于这种答案较浅的搜索，考虑迭代加深；
那么我们将这个作为限制的深度；
对于估价函数，就是你每次移动后，还有多少个位置与目标状态不同，所以我们用当前的步数+估价函数的值；
一旦超过我们限制的深度，我们直接return；
这样避免一直对一个错误的分支一直搜索；也让代码加快了很多；
dfs算阶搜索题目整理https://www.cnblogs.com/Tyouchie/p/11117966.html ；
c++代码；

#include<bits/stdc++.h>
using namespace std;
const int s1[5][5]=
{{1,1,1,1,1},
 {0,1,1,1,1},
 {0,0,2,1,1},
 {0,0,0,0,1},
 {0,0,0,0,0}};
int dx[8]={2,-2,1,-1,2,1,-1,-2},dy[8]={1,-1,2,-2,-1,-2,2,1};
int T,s2[50][50],flag;
template<typename T>inline void read(T &x) {
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
}
inline int check() {
    int ans=0;
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++) {
            if(s2[i][j]!=s1[i][j])
                ans++;
        } 
    return ans;
}
inline void dfs(int x,int y,int deep,int s) {
    if(flag) return ;
    int a=check();
    if(!a) {
        flag=1;
        return ;
    }
    if(s+a>deep+1) return ;
    for(int i=0;i<8;i++) {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<0||yy<0||xx>4||yy>4)  continue;
        swap(s2[xx][yy],s2[x][y]);
        dfs(xx,yy,deep,s+1);
        swap(s2[xx][yy],s2[x][y]);
    }
}
int main() {
    read(T);
    while(T--) {
        char s3[15],tx,ty;
        for(int i=0;i<5;i++) {
            scanf("%s",s3);
            for(int j=0;j<5;j++) {
                if(s3[j]=='*') {
                    s2[i][j]=2;//记录下空位；
                    tx=i;
                    ty=j;
                }
                else s2[i][j]=s3[j]-48;
            }
        }
        int deep=1;
        while(deep<=15) {
            flag=0;
            dfs(tx,ty,deep,0);
            if(flag) break;
            deep++;
        }
        if(flag) printf("%d\n",deep);
        else puts("-1");
    }
    return 0;
}