2020年第十一届蓝桥杯国赛—c++B组—试题F：皮亚诺曲线距离

这道题我写了一个多小时，还是自己太菜了，两个样例都过了，三阶皮亚诺随便取了两个点，距离也是正确的，如果有大佬找到了我的问题，欢迎指正

以下是我的思路

思路

总体就是求出两个点到原点的距离，然后相减即可

那么具体如何求呢，可以发现，当 $k>1$ 的时候，皮亚努曲线图都可以分解为 $3\times 3$ 的 $k?1$ 阶皮亚诺曲线块

那么假设当前是第 $k_i$ 阶，那么我们可以求出经过了多少个 $k_i?1$ 阶块走到了当前坐标所在的 $k_i?1$ 阶块

只要求出了走过了几个块，那么因为每一个块中距离都是 $(k_i?1)(k_i?1)$ 个， 就能求出在当前块之前已经走过了多少个块

然后再递归 $k_i?1$ 阶的情况

直到 $k==1$ 时，就划归为了一阶皮亚诺曲线到出发点的距离

因为一阶皮亚诺曲线根据进出方向和矩阵方向，有四种不同的情况，经过分析其实可以写一个坐标的变化，将其都变换为某一种情况求解即可

代码

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;

int k;
int x1, y1;
int x2, y2;

// 一阶皮亚诺距离函数 
int get_k1(int x,int y) {
	int dis = 0;
	if(x == 0) dis = y;
	if(x == 1) dis = 3 + (2 - y);
	if(x == 2) dis = 6 + y;
	return dis;
}

// 确定其前面几个 k 块
int get_block(int x, int y, int &d) {
	int sum = 0;
	if(x == 0 && y == 0) {
		d = 0;
		sum = 0;
	}
	if(x == 0 && y == 1) {
		d = 1;
		sum = 1;
	}
	if(x == 0 && y == 2) {
		d = 0;
		sum = 2;
	}
	if(x == 1 && y == 2){
		d = 2;
		sum = 3;
	}
	if(x == 1 && y == 1) {
		d = 3;
		sum = 4;
	}
	if(x == 1 && y == 0) {
		d = 2;
		sum = 5;
	}
	if(x == 2 && y == 0) {
		d = 0;
		sum = 6;
	}
	if(x == 2 && y == 1) {
		d = 1;
		sum = 7;
	}
	if(x == 2 && y == 2) {
		d = 0;
		sum = 8;
	}
	return sum;
}

// 坐标转换. d 是用来确定哪一种情况，详细值参照题目图
void trans(LL &x, LL &y,int d) {
	if(d == 0) return;
	if(d == 1) {
		x = 2 - x;
		return;
	}
	if(d == 2) {
		y = 2 - y;
		return;
	}
	if(d == 3) {
		x = 2 - x;
		y = 2 - y;
		return;
	}
} 

// 递归求解
LL get(LL x, LL y, int k,int d) {
	
	LL sum = 0;
	if(k == 1) {
		trans(x,y,d);
		sum += get_k1(x,y);
		return sum;
	}
	
	LL sub = pow(3,k - 1);
	int tx = x / sub, ty = y / sub;
	int blocks = get_block(tx,ty,d);
	sum = blocks * sub * sub;
	sum += get(x % sub,y % sub,k - 1,d);
	
	return sum;
}

int main()
{
	cin >> k;
	cin >> x1 >> y1;
	cin >> x2 >> y2;
	get(x1,y1,k,0);
	cout << abs(get(x1,y1,k,0) - get(x2,y2,k,0)) << endl;
	return 0;
} 
/*
2
3 4
0 0
*/