Astar

本质上大概是搜索优化。我们将bfs使用的队列改为优先队列，并使用结构体存储节点，重载 ‘<’ 小于号。

然后我们提高搜索效率的方法就是通过一个估价函数，评估当前情况与答案情况的差异，然后选取差异最小(或根据题目，并基于个人经验选取能够更快找到答案的情况)

由于优先队列存在复杂度，有时候估价函数写得不好反而会爆炸。所以谨慎选择即可。

例题: P2324 SCOI2005骑士精神 这里我们采用了 $A*$，估价函数的标准就是棋盘上每一位的差异和

#include<bits/stdc++.h>
using namespace std;
int ux,uy,wx[10]={1,1,-1,-1,2,2,-2,-2},wy[10]={2,-2,2,-2,1,-1,1,-1},T;
struct TAT
{
	int x[10][10];
	bool operator<(TAT b) const
	{
		for(int i=1;i<=5;++i)
		{
			for(int j=1;j<=5;++j)
			{
				if(x[i][j]!=b.x[i][j]) return x[i][j]<b.x[i][j];
			}
		}
		return 0;
	} 
}s,f;
int h(TAT x)
{
	int res=0;
	for(int i=1;i<=5;++i)
	{
		for(int j=1;j<=5;++j)
		{
			if(s.x[i][j]!=x.x[i][j]) ++res;
		}
	}
	return res;
}
struct node
{
	TAT x;
	int t;
	bool operator<(node b) const
	{
		return t+h(x)>b.t+h(b.x);
	}
}x;

int main()
{
	s.x[1][1]=s.x[1][2]=s.x[1][3]=s.x[1][4]=s.x[1][5]=1;
	s.x[2][1]=0;s.x[2][2]=s.x[2][3]=s.x[2][4]=s.x[2][5]=1;
	s.x[3][1]=s.x[3][2]=0;s.x[3][3]=2;s.x[3][4]=s.x[3][5]=1;
	s.x[4][1]=s.x[4][2]=s.x[4][3]=s.x[4][4]=0;s.x[4][5]=1;
	s.x[5][1]=s.x[5][2]=s.x[5][3]=s.x[5][4]=s.x[5][5]=0;
    scanf("%d",&T);
    while(T--)
    {
    	for(int i=1;i<=5;++i)
	    {
	    	for(int j=1;j<=5;++j)
	    	{
	    		char c;
				cin>>c;
	    		if(c!='*') f.x[i][j]=c-'0';
	    		else f.x[i][j]=2;
	    		//printf("%d ",f.x[i][j]);
			}
			//putchar('\n');
		}
		node sdsdsd;
		sdsdsd.x=f,sdsdsd.t=0;
		priority_queue<node>q;
		map<TAT,bool>ex;
		q.push(sdsdsd);
		while(!q.empty())
		{
			x=q.top();
			q.pop();
			if(x.t>15)
			{
				printf("%d\n",-1);
//				for(int i=1;i<=5;++i)
//				{
//					for(int j=1;j<=5;++j)
//					{
//						printf("%d ",x.x.x[i][j]);
//					}
//					putchar('\n');
//				}
				break;
			}
			if(h(x.x)==0)
			{
				printf("%d\n",x.t);
				break;
			}
			for(int i=1;i<=5;++i)
			{
				for(int j=1;j<=5;++j)
				{
					if(x.x.x[i][j]==2) ux=i,uy=j;
				}
			}
			for(int i=0;i<8;++i)
			{
				int lx=ux+wx[i],ly=uy+wy[i];
				if(lx<1||lx>5||ly<1||ly>5) continue;
				swap(x.x.x[lx][ly],x.x.x[ux][uy]);
				if(!ex[x.x]) 
				{
					ex[x.x]=1;
					node sd2;
					sd2.x=x.x;sd2.t=x.t+1;
					q.push(sd2);
				}
				swap(x.x.x[lx][ly],x.x.x[ux][uy]);
			}
		}
	}
	return 0;
}