第一个A*，纪念下。

A*要保证最短路一定要估价函数小于等于实际值，越接近越好

估价函数取Manhattan距离除以二。

//Rey

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 8;bool C[N][N];struct node{   int g,h;   int x, y;   bool operator < (const node& rhs) const{      if(g + h > rhs.g + rhs.h) return true;      if(g + h < rhs.h + rhs.g ) return false;      return g > rhs.g;   }};int tax,tay;inline void getH(node& o){   o.h = (abs(o.x-tax)+abs(o.y-tay))>>1;}#define joinC(n) C[n.x][n.y] = trueint dx[] = {
   1,2, 1, 2,-1,-2,-1,-2};int dy[] = {
   2,1,-2,-1,-2,-1, 2, 1};int bfs(node &start){   priority_queue
         
           Q;   memset(C,false,sizeof(C));   Q.push(start);   joinC(start);   node cur,nxt;   int i,nx,ny;   while(Q.size()){      cur = Q.top();Q.pop();      if(cur.x == tax && cur.y == tay) return cur.g;      for(i = 0; i < N; i++){         nx = cur.x + dx[i];         ny = cur.y + dy[i];         if(nx >= N || nx < 0 || ny >= N || ny < 0 || C[nx][ny]) continue;         nxt.x = nx ; nxt.y = ny; nxt.g = cur.g+1 ; getH(nxt);         joinC(nxt);         Q.push(nxt);      }   }   return -1;}int main(){   node start;   char fro[3],to[3];   char ch;   int n;   while(~scanf("%s",fro)){      scanf("%s",to);      sscanf(fro,"%c",&ch);      sscanf(fro+1,"%1d",&n);      start.x = ch -'a';      start.y = n-1;      start.g = 0;      sscanf(to,"%c",&ch);      sscanf(to+1,"%1d",&n);      tax = ch - 'a';      tay = n-1;      getH(start);      printf("To get from %s to %s takes %d knight moves.\n",fro,to,bfs(start));   }   return 0;}