【BFS, 贪心】马步距离

题目

2135. 马步距离

---

在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。

如下图所示，从标号为 $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$ 。

输出格式

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

数据范围

$-10^7 < x_p,y_p,x_s,y_s < 10^7$

输入样例：

1 2 7 9

输出样例：

5

解题

方法一：贪心 BFS

思路

这题的数据范围是 $10^7$，直接 BFS 肯定会 TLE，于是想到可以以起始点为原点，然后算出终点的相对坐标。
但是这样数据范围还是太大，此时我们发现，马步是中心对称的，也就是说终点坐标可以绝对值化或者交换横纵坐标。
这样以来就可以把终点相对坐标缩小到一个很小的范围在进行 BFS 了。

代码

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, int> PIII;

const int DIRS[][2] = {{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}};
int xp, yp, xs, ys;

int main() {
    scanf("%d%d%d%d", &xp, &yp, &xs, &ys);
    int dx = abs(xp - xs), dy = abs(yp - ys);
    int step = 0;
    while (dx > 4 || dy > 4) {
        if (dx < 0) dx = -dx;
        if (dy < 0) dy = -dy;
        if (dx > dy) {
            dx -= 2;
            --dy;
        } else {
            dy -= 2;
            --dx;
        }
        ++step;
    }
    queue<PIII> que;
    unordered_set<string> vis;
    que.push({{0, 0}, step});
    vis.insert(to_string(xp) + ',' + to_string(yp));
    while (!que.empty()) {
        auto pr = que.front();
        que.pop();
        int x = pr.first.first, y = pr.first.second, step = pr.second;
        if (x == dx && y == dy) {
            printf("%d\n", step);
            return 0;
        }
        for (auto& DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            string pos = to_string(nx) + ',' + to_string(ny);
            if (vis.find(pos) == vis.end()) {
                que.push({{nx, ny}, step + 1});
                vis.insert(pos);
            }
        }
    }
    
    return 0;
}

方法二：贪心 打表

思路

即然坐标已经被缩到足够小了，那么 BFS 的过程也可以打表代替。

代码

#include <iostream>

using namespace std;

const int DICT[][5] = {{0, 3, 2, 3, 2},
                       {3, 2, 1, 2, 3},
                       {2, 1, 4, 3, 2},
                       {3, 2, 3, 2, 3},
                       {2, 3, 2, 3, 4}};
int xp, yp, xs, ys;

int main() {
    scanf("%d%d%d%d", &xp, &yp, &xs, &ys);
    int dx = abs(xp - xs), dy = abs(yp - ys);
    int step = 0;
    while (dx > 4 || dy > 4) {
        if (dx < 0) dx = -dx;
        if (dy < 0) dy = -dy;
        if (dx > dy) {
            dx -= 2;
            --dy;
        } else {
            dy -= 2;
            --dx;
        }
        ++step;
    }
    printf("%d\n", step + DICT[dx][dy]);
    
    return 0;
}