题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1085
搜索，IDA*，估价就是最少需要跳的步数；
代码意外地挺好写的，memcmp 用起来好方便啊。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int goal[6][6]= {{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[10]={2,-2,2,-2,1,-1,1,-1},dy[10]={1,-1,-1,1,2,-2,-2,2},T,a[6][6],ans,k; bool fl; bool pd(int dep) { int cnt=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) if(a[i][j]!=goal[i][j])cnt++; return cnt+dep<=k; } void dfs(int dep,int x,int y) { if(dep==k&&memcmp(goal,a,sizeof a)==0) { fl=1; return; } for(int i=0;i<8;i++) { if(fl||dep>=k)return;// int xx=x+dx[i],yy=y+dy[i]; if(xx<0||yy<0||xx>4||yy>4)continue;//! swap(a[x][y],a[xx][yy]); if(pd(dep))dfs(dep+1,xx,yy); swap(a[x][y],a[xx][yy]); } } int main() { scanf("%d",&T); while(T--) { char ch[10]; fl=0; int si,sj; for(int i=0;i<5;i++) { scanf("%s",&ch); for(int j=0;j<5;j++) if(ch[j]=='*')a[i][j]=2,si=i,sj=j; else a[i][j]=ch[j]-'0'; } for(k=1;k<=15;k++) { dfs(0,si,sj);//0 if(fl)break; } if(!fl)printf("-1 "); else printf("%d ",k); } return 0; }