第十三届蓝桥杯省赛 JAVA A组 - 蜂巢

✍个人博客https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址蓝桥杯题解集合
📝原题地址蜂巢
📣专栏定位为想参加蓝桥别的小伙伴整理常考算法题解祝大家都能取得理想成绩
❤️如果有收获的话欢迎点赞👍收藏📁您的支持就是我创作的最大动力💪

问题描述

蜂巢由六边形拼接而成定义蜂巢中的方向0表示正西方向1表示西偏北60°2表示东偏北60°3表示正东4表示东偏南60°5表示西偏南60°。

对于给定的一点O以O为原点定义坐标系如果一个点A由O点先向d方向走p步再向(d + 2) mod 6方向d的顺时针120°向走q步到达则这个点的坐标定义为(d, p, q)。在蜂窝中一个点的坐标可能有多种。 图给出了点B(0, 5, 3)和点C(2, 3, 2)的示意。

给定点(d1, p1, q1)和点(d2, p2, q2)请问他们之间最少走多少步可以到达

输入格式

输入一行包含 6 个整数 d1,p1,q1,d2,p2,q2 表示两个点的坐标相邻两个整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示两点之间最少走多少步可以到达。

数据范围

对于 25% 的评测用例p1,p2≤10³
对于 50% 的评测用例p1,p2≤10⁵
对于 75% 的评测用例p1,p2≤10⁷
对于所有评测用例0≤d1,d2≤50≤q1<p1≤10⁹0≤q2<p2≤10⁹。

输入样例

0 5 3 2 3 2

输出样例

7

思路

这道题从图上来看其实并不难假设我要从 B 到 C 找到最短路径实际上就只能从右下走但是难就难在这题没有给定坐标系坐标系需要我们自己分析构建。

我们以 O 点为原点以每个蜂巢的中心点作为每一处坐标构建坐标系

观察上图可知如果直接用曼哈顿距离公式来计算两点之间的距离是不正确的但可以发现如下规律假设两点之间的横坐标之差的绝对值为 $dx=|x1-x2|$纵坐标之差的绝对值为 $dy=|y1-y2|$

• 如果 dx 大于 dy则两点之间的距离为 $(dx+dy)/2$
• 如果 dx 小于 dy则两点之间的距离为 $dy$
• 如果 dx 等于 dy上面的两种公式都能得到正确答案

举个例子假设从 (-1,1) 到 (1,-1)其 dx 和 dy 分别为 2 和 3。故 dy 大于 dx 则最少要走 3 步。

再举个例子假设从 (-1,1) 到 (2,0)其 dx 和 dy 分别为 3 和 1。故 dx 大于 dy则最少要走 (1+3)/2=2 步。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
LL d1, p1, q1, d2, p2, q2;
LL dx[] = { -2,-1,1,2,1,-1 }, dy[] = { 0,1,1,0,-1,-1 };

void walk(LL d, LL s, LL& x, LL& y)
{
    x += dx[d] * s;
    y += dy[d] * s;
}

int main()
{
    cin >> d1 >> p1 >> q1 >> d2 >> p2 >> q2;

    //计算第一个坐标
    LL x1 = 0, y1 = 0;
    walk(d1, p1, x1, y1);
    walk((d1 + 2) % 6, q1, x1, y1);

    //计算第二个坐标
    LL x2 = 0, y2 = 0;
    walk(d2, p2, x2, y2);
    walk((d2 + 2) % 6, q2, x2, y2);

    //计算dx和dy
    LL dx = abs(x1 - x2), dy = abs(y1 - y2);

    //根据计算结果输出对应答案
    if (dx >= dy)  cout << (dx + dy) / 2 << endl;
    else cout << dy << endl;

    return 0;
}