当guess>limit-deep的时候return就好了。
guess是估价函数，值为不在自己地盘上的骑士个数。limit是本次迭代阈值。deep是已经走了多少步。
这个优化是显然的。因为一次跳跃最多可以复原一个骑士。假设最好的情况，所有的骑士都能一步跳回去，如果这样还不能在阈值步数内复原，那不论如何都没法复原了——也就没有继续搜下去的必要了。
放上代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<map>
using namespace std;
map<long long,bool>vis;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} long long goal; int u[]={,-,-,,,,,-,-};
int w[]={,-,-,-,-,,,,}; int s[][]={ {, , , , , },
{, , , , , },
{,-, , , , },
{,-,-, , , },
{,-,-,-,-, },
{,-,-,-,-,-} }; int q[][];
char c[];
int ans; void dfs(int deep,int limit,int guess,int x,int y){
if(guess>limit-deep) return;
if(guess==){
ans=ans>deep?deep:ans;
return;
}
for(register int e=;e<=;++e){
int a=x+u[e],b=y+w[e];
if(a>&&b>&&a<&&b<){
int New=guess;
/*if(q[x][y]==s[x][y]&&q[x][y]!=s[a][b]) --New;
if(q[x][y]!=s[x][y]&&q[x][y]==s[a][b]) ++New;*/
if(q[a][b]==s[a][b]&&q[a][b]!=s[x][y]) ++New;
if(q[a][b]!=s[a][b]&&q[a][b]==s[x][y]) --New;
q[x][y]=q[a][b]; q[a][b]=;
if(New<=limit-deep-) dfs(deep+,limit,New,a,b);
q[a][b]=q[x][y]; q[x][y]=;
}
}
} int main(){
int T=read();
while(T--){
ans=0x7fffffff;
//vis.clear();
int x,y,start=;
long long val;
for(int i=;i<=;++i){
scanf("%s",c+);
for(int j=;j<=;++j){
if(c[j]=='*'){
x=i;y=j;
q[i][j]=;
}
else q[i][j]=(c[j]-''==?:-);
if(q[i][j]!=&&q[i][j]!=s[i][j]) start++;
}
}
/*for(int i=1;i<=5;++i,printf("\n"))
for(int j=1;j<=5;++j) printf("%d ",q[i][j]);*/
if(start==){
printf("0\n");
continue;
}
for(int i=;i<=;++i){
//vis.clear();
dfs(,i,start,x,y);
if(ans!=0x7fffffff){
printf("%d\n",ans);
break;
}
}
if(ans!=0x7fffffff) continue;
printf("-1\n");
}
}