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

全栈程序员-站长 • 2026年3月18日上午11:16 • 未分类 • 阅读 2

F: 皮亚诺曲线距离

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

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

我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是(0, 0)，右上角坐标是 (3k − 1, 3k − 1)，右下角坐标是 (3k − 1, 0)，左上角坐标是(0, 3k − 1)。

给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是多少？

题解

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

#include 
     #include 
     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< 
    
    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< 
      
      long 
      long s2 
      = 
      calc 
      (x2 
      ,y2 
      ,level 
      , 
      0 
      ) 
      ; cout 
      <<s2 
      -s1 
      ; 
      return 
      0 
      ; 
      }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216702.html原文链接：https://javaforall.net

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

F: 皮亚诺曲线距离

题解

关于作者

全栈程序员-站长

发表回复

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

F: 皮亚诺曲线距离

题解

关于作者

全栈程序员-站长

相关推荐

ubuntu 挂在smb服务器的方法[通俗易懂]

CreateCompatibleDC用法

python学员管理系统流程图_python员工管理系统

软件测试流程设计—黑盒测试用例设计方法「建议收藏」

RedisClient 可视化Redis工具下载「建议收藏」

python获取文件名后缀名_python获取文件名不含后缀名

发表回复