View Code of Problem 1001

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

int vis[10][10];
int dir[8][2] = {1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1, -2,1, -1,2};
char start[3], end[3];
int sx,sy,ex,ey;

struct Node{
    int x,y;
    int step;
    int f,g,h;// f = g + h;
    //G 起点到当前点的费用
    //H 当前点到终点的估计费用【此处是欧几里得距离】

    Node(){}
    Node(int _x, int _y, int _step, int _g, int _h) {
        x = _x; y = _y; step = _step;

        f = _g + _h;
        g = _g; h = _h;
    }
//构造优先队列
    bool operator <(const Node &a) const {
        return a.f < f;
    }
};

bool inMap(int x, int y)
{
    if(x <= 0 || x > 8 || y <= 0 || y > 8) return false;
    return true;
}

//从(x,y) 到终点的估计费用 【欧几里得距离】
int getH(int x, int y)
{
    double x1 = x, x2 = ex, y1 = y, y2 = ey; //写的有点丑。。。
    double dist = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))*10;
    return (int)dist;
}
void aStart()
{
    priority_queue<Node> q;
    while(!q.empty()) q.pop();

    Node now ,next;
    now = Node(sx,sy,0, 0, getH(sx,sy));

    memset(vis, 0, sizeof(vis));
    vis[sx][sy] = 1;
    q.push(now);

    while(!q.empty())
    {
        now = q.top(); q.pop();

        for(int i = 0; i < 8; i++)
        {
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];

            if(!vis[next.x][next.y] && inMap(next.x, next.y))
            {
                vis[next.x][next.y] = 1;
                next.step = now.step + 1;
                next.g = now.g + 23;
                next.h = getH(next.x, next.y);
                next.f = next.g + next.h;
                q.push(next);

                if(next.x == ex && next.y == ey)
                {
                    printf("To get from %c%c to %c%c takes %d knight moves.\n", start[0], start[1], end[0], end[1], next.step);
                    return;
                }
            }
        }
    }
    return;
}
int main()
{
    while(scanf("%s%s", start, end) != EOF)
    {
        sx = start[0] - 'a' + 1;
        sy = start[1] - '0';

        ex = end[0] - 'a' + 1;
        ey = end[1] - '0';

        if(sx == ex && sy == ey)
        {
            printf("To get from %c%c to %c%c takes 0 knight moves.\n", start[0], start[1], end[0], end[1]);
            continue;
        }

        aStart();
    }
    return 0;
}