我把这个当做IDA*的模板题的说，说说我个人对IDA*的理解
IDA*是一个DFS，和A*一样，它也有一个乐观的估价函数。这里这个估价函数是用来限制状态的扩展的，如果当前代价加上乐观的估计都无法在规定层数内出解，我们就不向更深搜索了。这里取位置有差异的骑士个数作为估价函数即可，注意是骑士个数，因为在最后一步的时候我们有两个差异位置，然而实际上我们只要让一个骑士跳一步就可以完成了。这里我偷懒直接在差异位置上减掉了$1$......
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int goal[][]=
{
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,}
};
const int mov[][]=
{{,},{,-},{-,},{-,-},{,},{,-},{-,},{-,-}};
int mapp[][]; char rd[];
int T,sx,sy,lim,able;
int dif()
{
int ret=;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
ret+=(mapp[i][j]!=goal[i][j]);
return ret;
}
void IDAstar(int x,int y,int stp)
{
if(stp>lim)
{
if(!dif()) able=true;
return ;
}
for(int i=;i<&&!able;i++)
{
int tx=x+mov[i][],ty=y+mov[i][];
if(tx>=&&tx<=&&ty>=&&ty<=)
{
swap(mapp[x][y],mapp[tx][ty]);
if(dif()+stp-<=lim) IDAstar(tx,ty,stp+);
swap(mapp[x][y],mapp[tx][ty]);
}
}
}
int main ()
{
scanf("%d",&T);
while(T--)
{
for(int i=;i<=;i++)
{
scanf("%s",rd+);
for(int j=;j<=;j++)
if(rd[j]=='*') mapp[i][j]=,sx=i,sy=j;
else mapp[i][j]=(rd[j]-'');
}
bool found=false;
if(!dif()) {puts(""); continue;}
for(int i=;i<=;i++)
{
lim=i,able=false,IDAstar(sx,sy,);
if(able) {printf("%d\n",i); found=true; break;}
}
if(!found) printf("-1\n");
}
return ;
}