2020年第十一屆藍橋杯國賽—c++B組—試題F：皮亞諾曲線距離

這道題我寫了一個多小時，還是自己太菜了，兩個樣例都過了，三階皮亞諾隨便取了兩個點，距離也是正確的，如果有大佬找到了我的問題，歡迎指正

以下是我的思路

思路

總體就是求出兩個點到原點的距離，然后相減即可

那么具體如何求呢，可以發現，當 k > 1 k > 1 k>1 的時候，皮亞努曲線圖都可以分解為 3 × 3 3 × 3 3×3 的 k ? 1 k - 1 k?1 階皮亞諾曲線塊

那么假設當前是第 k i k_i ki? 階，那么我們可以求出經過了多少個 k i ? 1 k_i - 1 ki??1 階塊走到了當前坐標所在的 k i ? 1 k_i - 1 ki??1 階塊

只要求出了走過了幾個塊，那么因為每一個塊中距離都是 ( k i ? 1 ) ( k i ? 1 ) (k_i - 1)(k_i - 1) (ki??1)(ki??1) 個， 就能求出在當前塊之前已經走過了多少個塊

然后再遞回 k i ? 1 k_i - 1 ki??1 階的情況

直到 k = = 1 k == 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
*/