IDA*是IDS的基础上加上满足A*算法的估值函数来剪枝的搜索算法。
这题代码量挺少的，可以看出整个IDA*的框架：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; char init[][],over[][]={
{""},
{""},
{"00*11"},
{""},
{""}
}; int h(){
int res=;
for(int i=; i<; ++i){
for(int j=; j<; ++j){
if(over[i][j]!=init[i][j]) ++res;
}
}
return res;
} int mxdep;
bool isok;
int dx[]={-,-,-,,,,,-};
int dy[]={-,,,,,-,-,-};
void dfs(int x,int y,int g){
if(g==mxdep){
if(!memcmp(init,over,sizeof(over))) isok=;
return;
}
if(isok) return;
for(int i=; i<; ++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx< || nx>= || ny< || ny>=) continue;
swap(init[x][y],init[nx][ny]);
if(g+h()<=mxdep) dfs(nx,ny,g+);
swap(init[x][y],init[nx][ny]);
}
} int main(){
int t;
scanf("%d",&t);
while(t--){
int x,y;
for(int i=; i<; ++i){
for(int j=; j<; ++j){
scanf(" %c",&init[i][j]);
if(init[i][j]=='*') x=i,y=j;
}
}
for(mxdep=,isok=; mxdep<= && !isok; ++mxdep){
dfs(x,y,);
}
if(isok) printf("%d\n",mxdep-);
else puts("-1");
}
return ;
}