2020第十一届蓝桥杯国赛（决赛）C/C++ B组F题皮亚诺曲线距离题解

F: 皮亚诺曲线距离

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

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

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

皮亚诺曲线总是从左下角开始出发，最终到达右上角。

我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是(0, 0)，右上角坐标是 (3k − 1, 3k − 1)，右下角坐标是 (3k − 1, 0)，左上角坐标是(0, 3k − 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 < 3k, x1, y1, x2, y2 ≤ 10¹⁸。
数据保证答案不超过 10¹⁸。

题解

这道题比赛时看了下感觉很难，而且隔壁做很久都没出来，便果断放弃，下来后看了下其实感觉也不是很难。你可以把问题分解为分别求从左下角的点到第一个点和第二个点的距离，再把距离相减。通过calc函数计算距离，计算时把整幅图看做是由9个较小的方格组成的，看看从左下角的方格到该点所在的方格所需要走几个方格，再乘以每个方格内部曲线的长度，接着递归调用函数再求在小方格中到该点所在更小的方格要走几格，最后把各步求得的结果加起来就好了。至于其中有的小方格方向和1阶的方向不太一样，其实它就是做了个对称变换，你把它变换回去就可以了，可以不用再分别判断。代码不保证完全正确，反正我试了下没发现问题，但我想如果输入的坐标值太大，有可能会超过范围而出错。

#include<iostream>
#include<cmath>
using namespace std;
long long calc(long long x,long long y,int level,int type)
{ 
   //x,y start from 0, total size:3^level*3^level,type=0-3:起点在左下角，左上角，右上角，右下角
    if(level==0)return 0;
    long long int step,base=pow(9,level-1);
    if(type==1)y=pow(3,level)-1-y;
    else if(type==2)x=pow(3,level)-1-x,y=pow(3,level)-1-y;
    else if(type==3)x=pow(3,level)-1-x;
    if(x<pow(3,level-1))
    { 
   
        if(y<pow(3,level-1))
        { 
   
            step=0*base;
            step+=calc(x,y,level-1,0);
        }
        else if(y<pow(3,level-1)*2)
        { 
   
            step=1*base;
            step+=calc(x,y-pow(3,level-1),level-1,3);
        }
        else
        { 
   
            step=2*base;
            step+=calc(x,y-pow(3,level-1)*2,level-1,0);
        }
    }
    else if(x<pow(3,level-1)*2)
    { 
   
        if(y<pow(3,level-1))
        { 
   
            step=5*base;
            step+=calc(x-pow(3,level-1),y,level-1,1);
        }
        else if(y<pow(3,level-1)*2)
        { 
   
            step=4*base;
            step+=calc(x-pow(3,level-1),y-pow(3,level-1),level-1,2);
        }
        else
        { 
   
            step=3*base;
            step+=calc(x-pow(3,level-1),y-pow(3,level-1)*2,level-1,1);
        }
    }
    else
    { 
   
        if(y<pow(3,level-1))
        { 
   
            step=6*base;
            step+=calc(x-2*pow(3,level-1),y,level-1,0);
        }
        else if(y<pow(3,level-1)*2)
        { 
   
            step=7*base;
            step+=calc(x-2*pow(3,level-1),y-pow(3,level-1),level-1,3);
        }
        else
        { 
   
            step=8*base;
            step+=calc(x-2*pow(3,level-1),y-pow(3,level-1)*2,level-1,0);
        }
    }
    //cout<<x<<' '<<y<<' '<<level<<' '<<type<<' '<<step<<endl;
    return step;

}
int main()
{ 
   
    int level;
    cin>>level;
    long long int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    long long s1=calc(x1,y1,level,0);
    //cout<<endl;
    long long s2=calc(x2,y2,level,0);
    cout<<s2-s1;
    return 0;
}

今天的文章2020第十一届蓝桥杯国赛（决赛）C/C++ B组F题皮亚诺曲线距离题解分享到此就结束了，感谢您的阅读。