算法题：马的移动

问题描述

在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。如右图所示，从标号为0的点出发，可以经过一步马步移动达到标号为1的点，经过两步马步移动达到标号为2的点。

任给平面上的两点p和s,它们的坐标分别为(x~p~,y~p~)和(x~s~,y~s~),其中，x~p~,y~p~,x~s~,y~s~均为整数。从(x~p~,y~p~)出发经过一步马步移动可以达到(x~p+1~,y~p+2~)、(x~p+2~,y~p+1~)、(x~p+1~,y~p−2~)、(x~p+2~,y~p−1~)、(x~p−1~,y~p+2~)、(x~p−2~,y~p+1~)、(x~p−1~,y~p−2~)、(x~p−2~,y~p−1~)。假设棋盘充分大，并且坐标可以为负数。现在请你求出从点p到点s 至少需要经过多少次马步移动？

输入格式

从文件中读入数据，文件中只包含4个整数，它们彼此用空格隔开，分别为x~p~,y~p~,x~s~,y~s~。并且它们的都小于10000000。

输出格式

输出文件中包含一个整数，表示从点p到点s至少需要经过的马步移动次数。

样例

输入

1 2 7 9

输出

5

解决方案

思路

大范围贪心，小范围广度优先搜索

代码

#include <iostream>
#include <queue>
#include <map>

using namespace std;


int main() {
    pair<int, int> p, s;
    cin >> p.first >> p.second >> s.first >> s.second;

    p.first -= s.first;
    p.second -= s.second;
    s.first = s.second = 100;
    if (p.first < 0) p.first = -p.first;
    if (p.second < 0) p.second = -p.second;
    p.first += 100;
    p.second += 100;
    long long ans = 0;
    while (p.first - s.first >= 100 || p.second - s.second >= 100) {
        if (p.first >= p.second) {
            p.first -= 2;
            if (p.second > 100) p.second -= 1;
            else p.second += 1;
        } else {
            p.second -= 2;
            if (p.first > 100) p.first -= 1;
            else p.first += 1;
        }
        ans++;
    }

    map<pair<int, int>, long long> dis;
    queue<pair<int, int>> q;
    pair<int, int> point = p;
    q.push(point);
    dis[point] = 1;

    while (!q.empty()) {
        point = q.front();
        q.pop();

        if (point.first == s.first && point.second == s.second)
            break;

        int offset_x[] = {2, 2, 1, 1, -1, -1, -2, -2};
        int offset_y[] = {-1, 1, -2, 2, -2, 2, -1, 1};
        for (int i = 0; i < 8; ++i) {
            pair<int, int> t;
            t.first = point.first + offset_x[i];
            t.second = point.second + offset_y[i];

            // 距离太远就跳过去
            if (t.first < 90 || t.first > 210 || t.second < 90 || t.second > 210)
                continue;

            if (dis[t] == 0) {
                dis[t] = dis[point] + 1;
                q.push(t);
            }
        }
    }

    cout << dis[point] - 1 + ans;
    return 0;
}