P2324 [SCOI2005]骑士精神(A*)

P2324 [SCOI2005]骑士精神

A*与爆搜的不同就是它有一个估价函数$h(x)$

这个估价函数一般设为从当前状态到终点状态的估计最短步数，这样可以有效剪枝

但估计值必须严格小于等于实际剩余步数，否则会剪枝过度而影响正确性

$g(x),f(x)$分别为剩余步数和已走步数，则：

$g(x)=f(x)+h(x)$

本题中的$h(x)$可以设为未归位的棋子数+1

因为每一步最多使一个棋子归位（除最后一步一次归位2个棋子）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int d1[]={,,,,-,-,-,-};

int d2[]={,-,,-,,-,,-};

char a[][]; int re,col[][];

inline bool is(int x,int y){return (x==&&y==)?(a[x][y]=='*'):(a[x][y]==col[x][y]+'');}

void dfs(int d,int s,int x,int y){//d当前步数，s已归位棋子个数

    if(d+-s>=re||d>) return ;//f(x)=d,g(x)=24-s

    if(s==) {re=min(re,d); return ;}

    for(int i=;i<;++i){

        int rx=x+d1[i],ry=y+d2[i],p=s;

        if(rx<||<rx||ry<||<ry) continue;

        p-=is(x,y)+is(rx,ry);

        swap(a[x][y],a[rx][ry]);

        p+=is(x,y)+is(rx,ry);

        dfs(d+,p,rx,ry);

        swap(a[x][y],a[rx][ry]);

    }

}

int main(){

    for(int i=;i<=;++i) for(int j=i;j<=;++j) col[i][j]=;

    col[][]=col[][]=;

    int T,sum,fx,fy;scanf("%d",&T);

    while(T--){

        sum=; re=;

        for(int i=;i<=;++i){

            scanf("%s",a[i]+);

            for(int j=;j<=;++j){

                sum+=is(i,j);

                if(a[i][j]=='*') fx=i,fy=j;

            }

        }dfs(,sum,fx,fy);

        if(re>) re=-;

        printf("%d\n",re);

    }return ;

}