A*搜索。
A*搜索的基础百度百科（实在偷懒没看论文之类的），在这里不说了。
A*搜索很关键的是h(n)估价函数的选取（表示现在到结束节点需要的距离）
设d(n)为实际到结束节点的距离。h(n)<=d(n)就又不会丢掉最优解，又可以中途就排除很多不行的答案。
bfs就是一个h(n)=0的A*搜索。。。。。（所有状态都会被加进去，错的离谱的也要）。。。。。
好感人。。。。
。。。说到哪了。。。。
如果俩个状态有n个不一样的地方，至少要走n-1步，这个估价函数相当好。
在这个程序具体实现中dep=d时，其实已经走了（d+1）步。。所以估价函数不用-1.
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std; const int dx[]={2,1,-1,-2,-2,-1,1,2},dy[]={1,2,2,1,-1,-2,-2,-1}; char EndStatus[5][10] = {
"11111",
"01111",
"00*11",
"00001",
"00000", }; struct Status {
char a[5][6];
int x,y; bool operator ==(Status b) {
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(a[i][j] != b.a[i][j]) return false;
return true;
} int differ(Status b) {
int res=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(a[i][j] != b.a[i][j]) res++;
return res;
} Status step(int d) {
Status res=*this;
res.x=x+dx[d],res.y=y+dy[d];
if(res.x<0 || res.x>4 || res.y<0 || res.y>4) return *this;
swap(res.a[x][y],res.a[res.x][res.y]);
return res;
} void get() {
for(int i=0;i<5;i++) {
scanf("%s",a[i]);
for(int j=0;j<5;j++) if(a[i][j]=='*') {
x=i; y=j;
}
}
} void get(char b[5][10]) {
for(int i=0;i<5;i++)
for(int j=0;j<5;j++) {
a[i][j]=b[i][j];
if(a[i][j]=='*') {x=i; y=j;}
}
}
}Start,End,t;
int lim,T; bool dfs(int dep,Status s) {
if(dep==lim) return s==End;
for(int d=0;d<8;d++) {
t=s.step(d);
if(!(t==s) && dep+t.differ(End)<=lim) if(dfs(dep+1,t)) return true;
}
return false;
} int main() {
End.get(EndStatus);
scanf("%d",&T);
while(T--) {
Start.get();
for(lim=0;lim<=15;lim++) if(dfs(0,Start)) break;
printf("%d\n",lim>15 ? -1 : lim); }
return 0;
}