2020年第十一届蓝桥杯决赛JAVABG题“皮亚诺曲线距离“的个人题解目录

2020国赛 JAVA B组 个人题解目录
【问题描述】
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3×3 的
方格中的每一个格子，最终到达右上角的一条曲线。

下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 3^2 × 3^2 的方格中的每一
个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 3^3 × 3^3 的方格中的每一
个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是
(0 , 0)，右上角坐标是 (3^k−1 , 3^k−1)，右下角坐标是 (3^k−1 , 0)，左上角坐标是
(0 , 3^k−1)。
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮
亚诺曲线走，距离是到少？
【输入格式】
输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。
第二行包含两个整数 x1 , y1 ，表示第一个点的坐标。

第三行包含两个整数 x2 , y2 ，表示第二个点的坐标。
【输出格式】
输出一个整数，表示给定的两个点之间的距离。
【样例输入】
1
0 0
2 2
【样例输出】
8
【样例输入】
2
0 2
0 3
【样例输出】
13
【评测用例规模与约定】
对于 30% 的评测用例，0 ≤ k ≤ 10。
对于 50% 的评测用例，0 ≤ k ≤ 20。
对于所有评测用例，0 ≤ k ≤ 100, 0 ≤ x1 ,y1 , x2 ,y2 <3^k , x1 ,y1 , x2 ,y2 ≤ 10^18 。
数据保证答案不超过 10^18 。

解析：对问题进行降阶，最终转化成一阶的问题。以下分析均已3阶和2阶进行举例递推:
由观察发现以下特性：
（1）所有大于一阶的曲线都具有相同的运动顺序：


（2）对于n阶，9个n-1阶的入口方向和出口位置是固定的，1到9的入口分别是左下，右下，左下，左上，右上，左上，左下，右下，左下，共四种情况。

降阶思路：
以sum记录总步数
（1）算出在n-1阶中，起点在第a块，终点在第b块。则sum+=（b-a）* (3^n-1)²
（2）将终点在第b块的位置转换成第a块等价的位置，并平移至a块
（3）将两点都平移到第一块等效位置
重复（1），（2），（3）递归至一阶。
sum+=计算一阶中两点相对位置的步数。
注：
1.可能有的同学会问如果在（2）中平移后终点到了起点前面怎么办？这个没关系，因为此时下一步sum+=（b-a）* (3^n-1)²中（b-a）是负的，相当于往回走。
2.如何计算在第几块？通过计算起横纵坐标分别位于x3^n-1和(x-1)3^n-1之间判断，如对于三阶，（20，5）横坐标位于2*（3²）与3*（3²）之间，那么它的块数是3，4，9中的一个，纵坐标再通过同样的算法可以确定唯一的一块。
3.如何平移？由于总共只有四种情况，此时又知道点在第几块，只需要对相应的块的坐标进行旋转或对称即可转换成对于块的等效位置，显然，转换平移后和转换前两点的相对位置不变。

（代码后续补上）