一道\(IDA*\)的入门题。
首先我们发现移动空格比移动马更容易。
然后考虑如何移动。爆搜马的位置是一种有效的做法。
但是直接爆搜很容易出现一个问题：搜索可能会在一些劣的情况下搜很久，或者搜进死胡同不出来。
这时候我们设计一个东西叫做估价函数\(g_S\)，如果当前局面的花费\(h_S\)加上估价函数大于花费上界\(f_S\)的话，这条选择支就是不优的。
然后我们可以枚举上界进行搜索。
由于随着上界的增长，花费的增长速度极快——每一层的花费都远大于上一层的花费。故而尽管上界具有单调性，但二分上界并不会更优。
（其实\(IDA*\)本质上就是玄学剪枝吧。）
#include<iostream>
#include<cstdio>
int nw[6][6];
const int mp[6][6]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,-1,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0},
};
const int dx[8]={-2,-2,-1,-1,1,1,2,2};
const int dy[8]={1,-1,2,-2,2,-2,1,-1};
inline int val(){
int rt=0;
for(int i=1;i<=5;++i){
for(int j=1;j<=5;++j){
if(mp[i][j]!=nw[i][j]){
++rt;
}
}
}
return rt;
}
inline int Min(int A,int B){
return A>B?A:B;
}
inline void Swap(int &X,int &Y){
X^=Y^=X^=Y;
}
inline bool srch(int dp,int X,int Y,int dm,int lst){
int Nval=val();
if(!Nval){
return 1;
}
if(dp>dm){
return 0;
}
for(int i=0;i<8;++i){
if(i+lst==7){
continue;
}
int NX=X+dx[i],NY=Y+dy[i];
if(NX<1||NY<1||NX>5||NY>5){
continue;
}
Swap(nw[X][Y],nw[NX][NY]);
Nval=val();
if(Nval+dp<=dm+1){
if(srch(dp+1,NX,NY,dm,i)){
return 1;
}
}
Swap(nw[X][Y],nw[NX][NY]);
}
return 0;
}
void init(){
char ch[6];
int SX,SY;
for(int i=1;i<=5;++i){
std::cin>>ch+1;
for(int j=1;j<=5;++j){
nw[i][j]=ch[j]-'0';
if(!isdigit(ch[j])){
nw[i][j]=-1;
SX=i,SY=j;
}
}
}
if(!val()){
puts("0");
return;
}
for(int i=1;i<=15;++i){
if(srch(1,SX,SY,i,-1)){
printf("%d\n",i);
return;
}
}
puts("-1");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}