Luogo P2324 [SCOI2005]骑士精神

　　所有想练习A*的人都先来敲一下这道题吧。

　　数据范围即便只有5*5，但朴素的爆搜还是会超时。

　　因此考虑剪枝。

　　对于这道题，肯定只要进行最优化剪枝，判断现在走的步数+剩下最少要走的步数，如果大于ans或者15就return；

　　那么，估价函数怎么写？

　　利用小学生的思想，将目前的图与目标状态对比一下，还有多少棋子没有归位，那么至少就要走几步（每次最多归位一个）

　　还有一个技巧：存储空格的位置，这样可以简化搜索。

　　CODE

#include<cstdio>

#include<iostream>

using namespace std;

const int g[][]=

{

    {,,,,,},

    {,,,,,},

    {,,,,,},

    {,,,,,},

    {,,,,,},

    {,,,,,},

};

const int fx[]={,,-,-,,,-,-},fy[]={,-,,-,,-,,-};

int t,a[][],ans,i,j,x,y;

char ch;

inline int h()

{

    int tot=;

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

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

    if (a[i][j]!=g[i][j]) ++tot;

    return tot;

}

inline void Astar(int k,int x,int y)

{

    if (!h()) ans=k<ans?k:ans;

    if (k+h()>ans) return;

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

    {

        int xx=fx[i]+x,yy=fy[i]+y;

        if (xx>&&yy>&&xx<=&&yy<=)

        {

            swap(a[x][y],a[xx][yy]);

            Astar(k+,xx,yy);

            swap(a[x][y],a[xx][yy]);

        }

    }

}

int main()

{

    scanf("%d",&t);

    while (t--)

    {

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

        {

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

            {

                cin>>ch;

                if (ch=='') a[i][j]=; else if (ch=='') a[i][j]=; else x=i,y=j,a[i][j]=;

            }

        }

        ans=;

        Astar(,x,y);

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

    }

    return ;

}