分形之城：遞歸超典型例題，還沒明白？手把手畫給你看！
- 2021 年 7 月 12 日
- 筆記
引用自Acwing，原題鏈接：
目錄：
- 題目
- 題解
- 代碼
題目
城市的規劃在城市建設中是個大問題。
不幸的是，很多城市在開始建設的時候並沒有很好的規劃，城市規模擴大之後規劃不合理的問題就開始顯現。
而這座名為 Fractal 的城市設想了這樣的一個規劃方案，如下圖所示：
當城區規模擴大之後，Fractal 的解決方案是把和原來城區結構一樣的區域按照圖中的方式建設在城市周圍，提升城市的等級。
對於任意等級的城市，我們把正方形街區從左上角開始按照道路標號。
雖然這個方案很爛，Fractal 規劃部門的人員還是想知道，如果城市發展到了等級 $N$，編號為 $A$ 和 $B$ 的兩個街區的直線距離是多少。
街區的距離指的是街區的中心點之間的距離，每個街區都是邊長為 $10$ 米的正方形。
輸入格式
第一行輸入正整數 $n$，表示測試數據的數目。
以下 $n$ 行，輸入 $n$ 組測試數據，每組一行。
每組數據包括三個整數 $N, A, B$，表示城市等級以及兩個街區的編號，整數之間用空格隔開。
輸出格式
一共輸出 $n$ 行數據，每行對應一組測試數據的輸出結果，結果四捨五入到整數。
數據範圍
- $1 \le N \le 31$
- $1 \le A,B \le 2^{2N}$
- $1 \le n \le 1000$
輸入樣例：
3
1 1 2
2 16 1
3 4 33
輸出樣例：
10
30
50
題解
這有啥不明白的，手把手畫出來！
首先明確，為啥能用遞歸：
- 我們想計算
n等級的坐標，知道n-1等級的坐標就行
然後思考怎麼遞歸？
咱們首先規定，每個等級的坐標系原點是獨特的，如下圖。
然後我們從特殊到一般，歸納推規律：
- 等級1這個塊塊，如果放到等級2里，有四種情況要討論
- 等級1放到等級2的左上象限，則相當於順時針旋轉了 90° ，並且還要沿 y 軸翻轉（為什麼要沿 y 軸翻轉呢？因為你注意每個編號的位置，不翻轉，形狀雖然對上了，但是編號順序沒對上）
- 等級1放到等級2的右上象限，則不用轉
- 等級1放到等級2的右下象限，則不用轉
- 等級1放到等級2的左下象限，則相當於逆時針旋轉了 90° ，並且還要沿 y 軸翻轉
轉完了，因為我們現在從等級1到等級2了，因此坐標系原點也移動了，所以要在等級1的原有坐標基礎上進行平移。
好了，我給你畫個圖，你就懂了。
然後你再去看代碼。
這裡補充一點數學知識：
- 對於點
(x, y)，沿原點順時針旋轉 90° ，將變為(y, -x) - 對於點
(x, y)，沿原點逆時針旋轉 90° ，將變為(-y, x) - 對於點
(x, y)，以 y 軸為對稱軸翻轉將變為(-x, y)
代碼
#include <iostream>
#include <cstring>
#include <cmath> // sqrt
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
PLL calc(LL n, LL m)
{
/*
* n: 等級
* m: 坐標，從0開始計數
*/
if (n == 0) return {0, 0};
LL len = 1ll << (n - 1); // 2^{n-1} 本等級內象限的邊長/2
LL cnt = 1ll << (2 * n - 2); // 4^{n-1} 本等級內象限容量
PLL pos = calc(n - 1, m % cnt); // 上一等級的坐標信息
LL x = pos.first, y = pos.second;
int z = m / cnt; // 處於哪個象限
// 左上象限順轉90°（y,-x）沿y對稱（-y,-x）更換原點（-y-len,-x+len）
if (z == 0)
return { - y - len, - x + len };
// 右上象限更換原點（x+len,y+len）
else if (z == 1)
return { x + len, y + len };
// 右下象限更換原點（x+len,y-len）
else if (z == 2)
return { x + len, y - len };
// 左下象限逆轉90°（-y,x）沿y對稱（y,x）更換原點（y-len,x-len）
return { y - len, x - len };
}
int main()
{
int N;
cin >> N;
while (N --)
{
LL n, m1, m2;
cin >> n >> m1 >> m2;
PLL pos1 = calc(n, m1 - 1);
PLL pos2 = calc(n, m2 - 1);
double delta_x = (double) (pos1.first - pos2.first);
double delta_y = (double) (pos1.second - pos2.second);
// 等級1中 len 是單位長度，且表示象限的一半長即為 10 / 2 = 5
printf("%.0lf\n", sqrt(delta_x * delta_x + delta_y * delta_y) * 5);
}
}
