poj2243 Knight Moves--A*

原题链接：​​http://poj.org/problem?id=2243​​

题意：给定一个起始点和目标点，求按照“日”字走法，最少的步骤。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

struct Node
{
  int x, y, step;
  int f, g, h;
  bool operator < (const Node & node)const//末尾要加const
  {
    return f > node.f;
  }
};

int dir[8][2] = { { -2,-1 },{ -2,1 },{ 2,-1 },{ 2,1 },{ -1,-2 },{ -1,2 },{ 1,-2 },{ 1,2 } };
int sx, sy;
int dx, dy;
bool vis[10][10];

int getH(const Node & node)
{
  return (abs(sx - node.x) + abs(sy - node.y)) * 10;
}

int aStar(int x, int y)
{
  priority_queue<Node> Q;
  Node cur, nex;
  vis[x][y] = 1;
  cur.x = x;
  cur.y = y;
  cur.step = 0;
  cur.g = 0;
  cur.h = getH(cur);
  cur.f = cur.g + cur.h;
  Q.push(cur);
  while (!Q.empty())
  {
    cur = Q.top();
    Q.pop();
    if (cur.x == dx&&cur.y == dy)
      return cur.step;

    for (int i = 0; i < 8; i++)
    {
      nex.x = dir[i][0] + cur.x;
      nex.y = dir[i][1] + cur.y;
      //if (nex.x >= 1 && nex.x <= 8 && nex.y >= 1 && nex.y <= 7 && !vis[nex.x][nex.y])
      if (nex.x >= 1 && nex.x <= 8 && nex.y >= 1 && nex.y <= 8 && !vis[nex.x][nex.y])
      {
        vis[nex.x][nex.y] = 1;
        nex.step = cur.step + 1;
        nex.g = cur.g + 23;
        nex.h = getH(nex);
        nex.f = nex.g + nex.h;
        Q.push(nex);
      }
    }
  }
  return -1;
}
int main()
{
  char ch1, ch2;
  int t1, t2;
  while (~scanf("%c%d %c%d", &ch1, &t1, &ch2, &t2))
  {
    getchar();
    sx = t1;
    sy = ch1 - 'a' + 1;
    dx = t2;
    dy = ch2 - 'a' + 1;
    
    memset(vis, 0, sizeof(vis));
    printf("To get from %c%d to %c%d takes %d knight moves.\n", ch1, t1, ch2, t2, aStar(sx, sy));
  }
  return 0;
}