分析
跳马，首先跳马写起来就很复杂了。我们跳空格就行了。然后，我一看这个题，15步以上就算-1，那好啊，直接写了个爆搜。
结果样例都跑不出来。。遂考虑启发式搜索。评估函数很显然，现在有多少个没归位，那我最少就要跳这么多次。然后再加个迭代加深吧。然后我因为dx,dy手残写错了自闭了半个多小时…
这个题目算是显示图的搜索技巧吧。主要是启发式搜索和迭代加深的使用。
就没了。
#include <bits/stdc++.h>
using namespace std;const int maxn = 10;int dx[]={1,1,-1,-1,2,2,-2,-2};int dy[]={2,-2,2,-2,1,-1,1,-1};char G[maxn][maxn];bool found = false;char a[6][6]={ '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'};bool check(){ for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) { if(G[i][j]!=a[i][j]) return false; } } return true;}bool eva(int now,int t){ int cnt = 0; for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) { if(G[i][j]!=a[i][j]) cnt++; } } if(cnt+now>t) return false; return true;}void dfs(int x,int y,int t,int stp){ if(t==stp) { if(check()) found = true; return; } if(found) return; for(int i=0;i<8;i++) { int nx = x+dx[i]; int ny = y+dy[i]; if(nx>=1 && nx<=5 && ny>=1 && ny<=5) { swap(G[nx][ny],G[x][y]); if(eva(stp,t)) dfs(nx,ny,t,stp+1); swap(G[nx][ny],G[x][y]); } }}int main(http://www.my516.com){ int T; cin>>T; while(T--) { int sx,sy; found = false; for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) { cin>>G[i][j]; if(G[i][j]=='*') sx = i,sy = j; } } for(int i=0;i<=15;i++) { dfs(sx,sy,i,0); if(found) { printf("%d\n",i); break; } } if(!found) printf("-1\n"); } return 0;}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687---------------------