题目链接：http://poj.org/problem?id=2243
启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
估价函数：从当前节点移动到目标节点的预估费用；这个估计就是启发式的。在寻路问题和迷宫问题中，我们通常用曼哈顿（manhattan）估价函数（下文有介绍）预估费用。
A*算法与BFS：可以这样说，BFS是A*算法的一个特例。对于一个BFS算法，从当前节点扩展出来的每一个节点（如果没有被访问过的话）都要放进队列进行进一步扩展。也就是说BFS的估计函数h永远等于0，没有一点启发式的信息，可以认为BFS是“最烂的”A*算法。
选取最小估价：如果学过数据结构的话，应该可以知道，对于每次都要选取最小估价的节点，应该用到最小优先级队列（也叫最小二叉堆）。在C++的STL里有现成的数据结构priority_queue，可以直接使用。当然不要忘了重载自定义节点的比较操作符。
A*算法的特点：A*算法在理论上是时间最优的，但是也有缺点：它的空间增长是指数级别的。
启发函数：f=g+h;其中g是起点到当前结点的直线距离，h是当前结点到目的结点的某种度量函数，在本题中采用曼哈顿距离。
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x,y,step;
int f,g,h;
bool operator<(const node & n)const { //优先队列，需要重载操作符
return step>n.step;
} }k;
int endx,endy;
int Heuristic(const node &a){ //manhattan估价函数
return (abs(a.x-endx)+abs(a.y-endy))*10;
}
bool isbond(const node &a){ //判断是否是边界
if(a.x<0||a.y>=8||a.x>=8||a.y<0)return 1;
return 0;
}
bool visit[10][10];
int dir[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
priority_queue<node> Q; //8个方向
int bfs()
{
while(!Q.empty())Q.pop();
Q.push(k);
node p,q;
while(!Q.empty())
{
p=Q.top();
Q.pop();
if(p.x==endx&&p.y==endy){
return p.step;
}
visit[p.x][p.y]=1;
for(int i=0;i<8;i++)
{
q.x=p.x+dir[i][0];
q.y=p.y+dir[i][1];
if(visit[q.x][q.y])continue;
if(isbond(q))continue;
q.g=p.g+23;
q.h=Heuristic(q);
q.step=p.step+1;
Q.push(q);
}
} }
int main()
{
string a,b;
while(cin>>a>>b)
{
k.x=a[0]-'a';
k.y=a[1]-'1';
endx=b[0]-'a';
endy=b[1]-'1';
k.step=k.g=0;
k.h=Heuristic(k);
k.f=k.g+k.h;
memset(visit,0,sizeof(visit));
cout<<"To get from "<<a<<" to "<<b<<" takes ";
cout<<bfs()<<" knight moves."<<endl;
}
return 0;
}