所有想练习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 ;
}