bzoj 1085 [SCOI2005]骑士精神——IDA*

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1085

迭代加深搜索。

估价函数是为了预计步数来剪枝，所以要优于实际步数。

没错，不是为了确定搜索顺序，而是为了可行性剪枝！这样的话-1的情况就不会很慢了。

　　这样的话估价函数也不能弄什么 每个不合法位置到最近合法位置的距离 或者 把这个距离/3当做步数 了呢……

总之估价函数弄成不合法位置的个数来表示预计步数是很好的。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int T,dist[][],kx,ky,lm,ans,pri;

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

char a[][];

bool flag;

int g0(int i,int j)

{

    if(j<i||(i==&&j==)||(i==&&j==))return ;return ;

}

int g1(int i,int j)

{

    if(j>i||(i==&&j==)||(i==&&j==))return ;return ;

}

int gx(int i,int j)

{

    if(i==&&j==)return ;return ;

}

int g(int i,int j)

{

    if(a[i][j]=='')return g0(i,j);if(a[i][j]=='')return g1(i,j);return gx(i,j);

}

void init()

{

    pri=;//

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

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

        {

            pri+=g(i,j);if(a[i][j]=='*')kx=i,ky=j;

        }

}

bool pd(int x,int y,int k)

{

    if(x+cz[k][]<=&&x+cz[k][]>=&&y+cz[k][]<=&&y+cz[k][]>=)return true;

    return false;

}

void dfs(int x,int y,int cnt,int base)

{

    if(cnt==lm&&!base){flag=;ans=cnt;return;}

    if(cnt>=lm)return;

    for(int i=;i<=;i++) if(pd(x,y,i))

    {

        int tx=x+cz[i][],ty=y+cz[i][],val;

        if(a[tx][ty]=='')val=base-g0(tx,ty)-gx(x,y)+g0(x,y)+gx(tx,ty);

        else val=base-g1(tx,ty)-gx(x,y)+g1(x,y)+gx(tx,ty);

        if(val+cnt<=lm)

        {

            a[x][y]=a[tx][ty];a[tx][ty]='*';

            dfs(tx,ty,cnt+,val);

            a[tx][ty]=a[x][y];a[x][y]='*';

            if(flag)return;

        }

    }

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        for(int i=;i<=;i++)scanf("%s",a[i]+);

        init();flag=;

        for(lm=;lm<=;lm++)

        {

            dfs(kx,ky,,pri);if(flag)break;

        }

        if(flag)printf("%d\n",ans);else printf("-1\n");

    }

    return ;

}