https://www.luogu.com.cn/problem/UVA10422
A*做法
双倍经验 只能说一摸一样，就是在输入输出上不一样，因为有空格所以建议使用getline之类的输入方式
很显然这题我们不能去移动骑士，那我们就移动空格，而移动空格的方法就是移动马的方法（横1竖2或者竖1横2）
然后我们用迭代加深枚举步数跑dfs，然后运用A*进行剪枝
A*嘛就是运用估价函数省去一些分支 感觉这个讲的很明白
而这个题的估价函数就是有几个位置和目标状态不一样
嗯，大概就这样，那就看代码吧
#include<iostream> #include<queue> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> using namespace std; struct node{ int x,y,sum; }; int T; char x; int a[9][9]; int mb[7][7]={//目标状态 {0,0,0,0,0,0}, {0,1,1,1,1,1}, {0,0,1,1,1,1}, {0,0,0,2,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0} }; int dx[9]={1,1,-1,-1,2,2,-2,-2};//马的走法 int dy[9]={2,-2,2,-2,1,-1,1,-1}; int chek(){//记录距离目标状态还差几步（估价函数） int chas=0;//差数 for(int j=1;j<=5;j++){ for(int q=1;q<=5;q++){ if(mb[j][q]!=a[j][q]){ chas++; } } } return chas; } int dfs(int bs,int x,int y,int bstop){ if(bs==bstop){//如果到了枚举的步数看看是否已达目标状态 if(chek()==0){ return 1; }else{ return 0; } } for(int j=0;j<=7;j++){ int tx=x+dx[j]; int ty=y+dy[j]; if(tx<=5&&tx>=1&&ty<=5&&ty>=1){ swap(a[x][y],a[tx][ty]);//移动空格 int yuj=chek();//预计还需几步 if((yuj+bs)<=bstop){//如果现在所用步数加上预计步数未超过枚举的步数 ，那我们运行 if(dfs(bs+1,tx,ty,bstop)==1)return 1; } swap(a[tx][ty],a[x][y]);//记得换回来，别影响后边的判断 } } return 0; } int x1,y1; bool flag=0; string a1; int main(){ cin>>T; getchar();//缓冲区里遗留了\n,应用getchar()给读入; for(int i=1;i<=T;i++){ for(int j=1;j<=5;j++){ getline(cin,a1); for(int q=1;q<=5;q++){//进行转换 x=a1[q-1]; if(x==' '){ a[j][q]=2; x1=j,y1=q; }else{ a[j][q]=x-'0'; } } } flag=0; if(chek()==0){ cout<<"Solvable in 0 move(s)."; flag=1; }else{ for(int ans=1;ans<=10;ans++){//枚举步数 if(dfs(0,x1,y1,ans)==1){ flag=1; cout<<"Solvable in "<<ans<<" move(s)."; break; } } } if(flag==0){ cout<<"Unsolvable in less than 11 move(s)."; } cout<<endl; } return 0; }