lp2324 SCOI2005 骑士精神

一道\(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;
}