UVA439 knightMoves (A*启发搜索)

第一个A*，纪念下。

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

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

//Rey

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
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] = true
int 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<node> 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.
",fro,to,bfs(start));
   }
   return 0;
}