侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【BFS, 贪心】马步距离

GabrielxD
2023-01-01 / 0 评论 / 0 点赞 / 222 阅读 / 1,027 字
温馨提示:
本文最后更新于 2023-01-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

2135. 马步距离


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

如下图所示,从标号为 00 的点出发,可以经过一步马步移动达到标号为 11 的点,经过两步马步移动达到标号为 22 的点。

QQ截图20200716134421.png

任给平面上的两点 ppss ,它们的坐标分别为 (xp,yp)(x_p,y_p)(xs,ys)(x_s,y_s) ,其中, xp,yp,xs,ysx_p,y_p,x_s,y_s 均为整数。

(xp,yp)(x_p,y_p) 出发经过一步马步移动可以达到 (xp+1,yp+2),(xp+2,yp+1),(xp+1,yp2),(x_p+1,y_p+2),(x_p+2,y_p+1),(x_p+1,y_p-2), (xp+2,yp1),(xp1,yp+2),(xp2,yp+1),(xp1,yp2),(xp2,yp1)(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)

假设棋盘充分大,并且坐标可以为负数。

现在请你求出从点 pp 到点 ss 至少需要经过多少次马步移动?

输入格式

只包含 44 个整数,它们彼此用空格隔开,分别为 xp,yp,xs,ysx_p,y_p,x_s,y_s

输出格式

输出一个整数,表示从点 pp 到点 ss 至少需要经过的马步移动次数。

数据范围

107<xp,yp,xs,ys<107-10^7 < x_p,y_p,x_s,y_s < 10^7

输入样例:

1 2 7 9

输出样例:

5

解题

方法一:贪心 BFS

思路

这题的数据范围是 10710^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;
}
0

评论区