做算法题最怕遇到这种题：看起来像几何，实际考的是递归；你以为要画图模拟，结果二维数组连一角的零头都开不下。《算法竞赛进阶指南》递推与递归章节里那道“分形之城”，我第一次见时盯着题面愣了半天，后来才发现，整道题就是一道“用递归把编号翻译成坐标”的模板题。分形结构、旋转翻转、编号映射、欧氏距离，一招拆开，其实特别清爽。这篇文章就把这道题的完整拆解、坐标变换推导、代码实现和踩坑记录一次讲透，不管你是刚接触递归、还是准备参加算法竞赛，都应该能把题解看懂并复现出来。
1. 题目到底在讲什么
1.1 分形城市的递归构造规则
先描述一下题目里的城市长什么样。等级为 1 的城市，是一个 2×2 的街区，里面住着 4 户房屋；等级为 2 的城市，是把 4 个等级为 1 的城市拼成一个 4×4 的大街区，里面住着 16 户房屋；等级为 n 的城市，就是 4 个等级为 n-1 的城市拼成的一个 2^n × 2^n 的大街区，住着 4^n 户房屋。
关键在于“怎么拼”。不是简简单单平移四份就完了，而是四个方向分别带有旋转和翻转：
- 左上角的子块：把上一等级城市顺时针旋转 90 度，再水平翻转。
- 右上角的子块：直接把上一等级城市平移过来。
- 右下角的子块：也是直接平移。
- 左下角的子块：把上一等级城市逆时针旋转 90 度，再水平翻转。
房屋按照某种固定顺序编号。题目给你等级 n，以及两户房屋的编号 A、B，让你求这两户房屋在 2^n × 2^n 网格中的直线距离。输出要求是距离乘以 10 之后四舍五入到整数。数据范围一般给到 n ≤ 31，A、B 可以接近 4^31 这个量级。
第一次看到这个题，很多人的第一反应是：我可以递归生成整张地图，然后数格子。这个思路方向没错，但工程量完全失控。2^31 的边长意味着地图上有大约 2^62 个格子，别说二维数组，你连一维数组都开不下任何像样的规模。所以必须换思路：不把整张图生成出来，而是直接回答“某一编号的房屋在哪个坐标”，一旦拿到两户的坐标，距离就出来了。
1.2 题眼：编号和坐标之间隐藏的递归关系
这类题的核心是：城市的构造是递归的，编号的分配规律也是递归的。编号 0 到 4^n-1 的房屋，按块分布时，天然可以分成四段：前 4^(n-1) 个编号在左上块，接着 4^(n-1) 个在右上块，再接着 4^(n-1) 个在右下块，最后 4^(n-1) 个在左下块。
这给了我们一个非常舒服的递归入口。假设我想求编号 m 在等级 n 城市里的坐标，我可以先把 m 压缩成它所在的子块编号和块内编号。子块编号决定坐标变换公式，块内编号继续递归到等级 n-1 里求解。递归边界是等级 0，此时城市只有一个点，编号只有 0，坐标固定为 (0,0)。
这就是“递推与递归”章节里典型的自相似结构：大城由四个小城拼成，每个小城内部又是“更小的城”，编号连续分段落在四块里，整个问题天然地缩小规模。你把求坐标的函数写成 calc(n, m)，在函数内部调用 calc(n-1, m % cnt)，只需要处理四种子块转换，问题就闭环了。
2. 别急着画图：先把问题抽象成递归函数
2.1 递归函数的设计与编号分块
直接看函数签名：
Point calc(LL n, LL m);这个函数返回编号为 m 的房屋在等级 n 城市中的坐标。坐标用两个数表示，x 代表行方向（向下），y 代表列方向（向右），原点在左上角。所有坐标都从 0 开始。
递归的第一步是判断边界。当 n == 0 时，城市只有一个点，编号只能是 0，返回 (0, 0)。
当 n > 0 时，我们先把当前城市切分成四个子块。子块的边长是：
LL len = 1LL << (n - 1); // 2^(n-1)每个子块内部有多少户房屋？
LL cnt = 1LL << (2 * n - 2); // 4^(n-1)于是编号 m 落在哪个子块就很清楚了：
LL block = m / cnt; // 0: 左上, 1: 右上, 2: 右下, 3: 左下 LL rest = m % cnt; // 子块内部编号rest 是一个小于 cnt 的编号，正好可以投入下一次递归。我们把 calc(n-1, rest) 的结果记为 p = (x0, y0)，它表示“这户房屋在子块内部的相对坐标”。接下来要做的事情，就是把相对坐标通过平移、翻转等变换，映射回当前等级的全局坐标。
这一步的本质是分治：每次把规模除以 4，递归深度最多 n 层，n 最大 31，完全不会栈溢出。这也是递归题里很典型的设计：与其把整张图算出来，不如让函数自己“问”自己更小规模的问题。
2.2 四种子块的坐标变换表
以 len = 2^(n-1)，p = (x0, y0) 为前提，四个子块的变换规则如下：
| 子块 | 变换方式 | 最终坐标 |
|---|---|---|
| 0（左上） | 等价转置 | (y0, x0) |
| 1（右上） | 整体右移 | (x0, y0 + len) |
| 2（右下） | 整体向右下移动 | (x0 + len, y0 + len) |
| 3（左下） | 翻转后再放回左下区域 | (2 * len - 1 - y0, len - 1 - x0) |
看完这张表，大多数人会卡在子块 0 和子块 3。右上、右下就是平移，非常好理解；但左上、左下为什么是那个公式？我解释一下。
先说右上和右下。右上块就是把子块整体向右平移 len 个单位，所以 x 不变，y 加 len。右下块同时向右和向下移动 len，所以 x 加 len，y 也加 len。这两个方向没有任何翻转，保持了上一等级城市的原始朝向。
再说左上。题目说左上块由上一等级城市“顺时针旋转 90 度再水平翻转”得到。这个复合变换落到“x 向下、y 向右”的坐标系里，等效结果就是“转置”，也就是把 (x0, y0) 变成 (y0, x0)。你可以用等级 2 的左上块手算验证：等级 1 的编号 0、1、2、3 原本在 2×2 小方块里的位置分别是 (0,0)、(0,1)、(1,1)、(1,0)，转置之后变成 (0,0)、(1,0)、(1,1)、(0,1)。这样四个点仍然填满左上 2×2 区域，编号顺序发生了旋转式变化，但整体没有重叠、没有空洞。
最后说左下。它的来源是“逆时针旋转 90 度再水平翻转”，等效变换是：
(x0, y0) -> (2*len - 1 - y0, len - 1 - x0)这个式子里的 2len - 1 是关键的平移修正。你可以把它理解为：先对坐标做一次翻转，得到的值变成负方向或超出边界，于是通过平移把它拉回当前子块的合法范围内。因为左下子块的行范围是 [len, 2len - 1]，列范围是 [0, len - 1]，最终公式直接给出了绝对坐标，不需要再额外加块偏移。
2.3 手算验证一个完整例子
光看公式容易晕，我带你手算一遍等级 2 里的几个编号，你就知道这个递归到底在干什么。
假设要求等级 2 城市中编号 5 的坐标。n=2，len=2，cnt=4。
- m=5，block=5/4=1，rest=5%4=1，说明它在右上子块。
- 递归求 calc(1, 1)，得到等级 1 中编号 1 的坐标。等级 1 中编号 1 是 (0, 1)。
- 右上块变换：(0, 1+2) = (0, 3)。
所以编号 5 在等级 2 的坐标是 (0, 3)。
再求编号 13。n=2，m=13，block=3，rest=1，说明它在左下子块。
- 递归求 calc(1, 1) = (0, 1)。
- 左下块变换：(2*2-1-1, 2-1-0) = (2, 1)。
所以编号 13 在等级 2 的坐标是 (2, 1)。
你会发现，整个过程中并不需要知道“等级 2 城市到底长什么样子”，只需要不断把编号变小，层层递归到边界，再一层层做坐标变换。这就是递归建模的价值：你不画整张图，但每个点的位置却能被精确计算出来。
3. 完整代码与距离输出细节
3.1 求解距离的数学处理
拿到两户坐标之后，距离就变成了纯粹的数学问题。设两户坐标为 (x1, y1) 和 (x2, y2)，欧氏距离为：
dist = sqrt((x1 - x2)^2 + (y1 - y2)^2)题目要求输出“距离乘以 10 后四舍五入到整数”。为什么要乘 10？因为坐标单位本身是“格点间距”，输入输出要求保留到一位小数的精度，而直接输出浮点数容易引起误差，所以让距离放大 10 倍后取整。比如真实距离 14.142135 秒，乘以 10 是 141.42135，四舍五入得到 141，实际输出就是 141。
这里有个细节值得注意：四舍五入不要简单写(int)(dist * 10)。正确的目的是“四舍五入”，不是向下取整。C++ 里可以用printf("%.0lf", dist)，也可以用dist + 0.5后转整数。对于非负浮点数，dist + 0.5的截断就是四舍五入。考虑到坐标差可能很大，直接平方后转 double 会有精度损失风险，我推荐先转成long double再计算，安全很多。
3.2 C++ 参考实现
完整代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long LL; struct Point { LL x, y; // x 为行（向下），y 为列（向右），原点在左上角 }; // 返回等级 n 城市中，编号 m（0 起始）的坐标 Point calc(LL n, LL m) { if (n == 0) return {0, 0}; LL len = 1LL << (n - 1); // 子块边长 2^(n-1) LL cnt = 1LL << (2 * n - 2); // 子块内房屋数量 4^(n-1) Point p = calc(n - 1, m % cnt); LL block = m / cnt; // 0 左上，1 右上，2 右下，3 左下 if (block == 0) { return {p.y, p.x}; } else if (block == 1) { return {p.x, p.y + len}; } else if (block == 2) { return {p.x + len, p.y + len}; } else { return {2 * len - 1 - p.y, len - 1 - p.x}; } } int main() { int T; cin >> T; while (T--) { LL n, a, b; cin >> n >> a >> b; // 如果题意编号从 1 开始，就减 1 转成内部下标 Point pa = calc(n, a - 1); Point pb = calc(n, b - 1); LL dx = pa.x - pb.x; LL dy = pa.y - pb.y; long double dist = sqrtl((long double)dx * dx + (long double)dy * dy) * 10.0L; long long ans = (long long)(dist + 0.5L); cout << ans << '\n'; } return 0; }这段代码的核心逻辑只有 calc 一个函数。你只需要确认四种子块变换公式没有写错，剩下的交给递归。
3.3 边界与数据范围检查
写这道题时，很多人会在数据范围上翻车。
先看 cnt 的计算。n 最大 31，2 * n - 2 最大是 60，1LL << 60大约等于 1.15e18，还在 long long 范围内。如果你图省事写1 << (2 * n - 2)，这里 1 是 int，左移 60 位直接溢出，行为未定义。所以必须写成1LL。
再看坐标差的平方。坐标最大可以到 2^31 - 1，平方大约是 4.6e18。两个方向的平方和接近 9.2e18，刚好在 long long 有符号范围内的边缘。虽然理论上是安全的，但为了稳妥，我在计算距离前把 dx、dy 转成了 long double，这样不会因为浮点精度问题导致最终答案差 1。
递归深度方面，n=31 最多向下递归 31 层，函数栈完全扛得住，不需要担心爆栈。
4. 防坑指南：四个必踩的雷
4.1 编号到底从 0 开始还是从 1 开始
这个坑最隐蔽。不同版本题面表述不一样，有的直接给“编号 0 到 4^n-1”，有的则从 1 开始。如果你把题面的 A 原样丢进 calc，坐标整体会偏移，答案自然错。稳妥做法是：读入后先减 1，再用内部函数处理；如果题目本来就是 0 起始，减 1 也无妨，只要别忘了统一。
我在实际做题中写了个小习惯：calc 函数内部约定编号从 0 开始，main 函数读入编号后立刻a--, b--。这样不管题面怎么描述，我只需要在入口处改这一行，后续逻辑完全不用动。
4.2 坐标轴方向不统一导致的公式混乱
网上很多题解的坐标定义是“x 向右，y 向下”，也有反过来定义的。如果你的坐标系和变换公式不匹配，左上块和左下块的结果会全部镜像，距离倒是可能不变，但你很难调试。
我的建议是：在代码里用注释写死坐标定义，比如“x 为行方向，向下为正；y 为列方向，向右为正”。然后所有变换公式都以这个定义为准。写题解时也把坐标定义放最前面，避免读者对着公式晕头转向。
4.3 四舍五入时的精度坑
有同学输出时写成(LL)dist，如果答案是 141.421，转成整数是 141，没问题；但如果答案是 140.500001，正确四舍五入应该是 141，直接截断却得到 140。虽然题目很少会出现精准卡在 0.5 边界的数据，但写代码要养成好习惯。
用dist + 0.5L这种方式，是假设 dist 非负且误差远小于 0.5。对于本题坐标范围，long double 的精度足够，卡边界的概率极低。如果你实在不放心，也可以用printf("%.0Lf", dist)，让库函数做舍入。
4.4 过度依赖肉眼模拟图像
很多初学者拿到分形题，第一件事就是试图打印或画出完整地图，然后对着图像找规律。这种方式在小规模下确实能帮你建立直觉，但一旦到了等级 4、等级 5，肉眼已经很难判断坐标规律了。我更推荐写一个辅助脚本或暴力程序，枚举前几等级的坐标并打印成表格，验证递归公式是否正确。这个方法我在做题时反复用，比盯着公式空想高效太多。
5. 这类题还能怎么延伸
5.1 与空间填充曲线的血缘关系
分形之城的编号顺序，本质上是某种带旋转的 Z-order 曲线，或者说四叉树结构的空间填充方式。你可以把编号看作对 2^n × 2^n 网格的四叉树编码：最高两位表示第一个四分之一区域，接着两位表示更小的区域……一直到最低位。递归 calc 的过程就是在解析这段编码。
明白了这一点，很多空间索引算法里的“Morton 码”你也能顺带理解。Z-order 曲线的 Morton 编码是把整数交错位运算得到位置，而分形之城多了一步旋转翻转，让曲线在局部区域产生更自然的连续性。了解这层关系之后，以后再碰到“给编号求坐标”“给坐标求编号”的题目，你很容易联想到四叉树和位运算。
5.2 反向问题：从坐标反推编号
如果把题目改成“给定等级 n 和坐标，求房屋编号”，你会怎么做？这时候 calc 的思路反过来用就行：根据点所在的子块，决定 block，再把坐标反向旋转翻转，得到子块内的相对坐标，最后递归进入下一层。在每一层把 block 记录成一个两位二进制，自顶向下拼起来就是最终编号。
这个反向版本是分形题常见的变形。练好正向 calc，反向思路基本是白送，只要小心坐标变换公式的逆运算别写错。建议你在本地把两个版本都写一遍，互相验证，能极大加深对坐标变换的理解。
5.3 对“递推与递归”学习路线的建议
如果你刚刷到这一节，我的建议是：先别急着看题解，自己从“编号分段 + 四块变换”这个角度硬推半小时；推不出来再看坐标变换表，然后把表抄下来，自己手算等级 2 的 4、13、15 等几个编号，直到你不再怀疑公式为止。
递归题的难点永远是“敢不敢把问题丢给下一层”。分形之城这类题目天然适合训练这种思维：看似复杂的大图，实际上只是四个小图的某种拼接。多做几道类似的题目，比如其他分形图形、矩阵旋转填充题，你会在某一次调试中突然觉得“递归也不过如此”。
我自己刷这题时最大的体会是：卡住的时候，别在脑子里转圈，拿张方格纸，把等级 2 的 16 个编号全部填进去。填完之后你会发现，左上块的编号顺序、左下块的镜像关系全部清清楚楚，那些公式不再需要死记。最后再分享一个小技巧：写一个只处理 n ≤ 3 的暴力生成程序，用它输出每个编号的坐标，再和递归函数的结果对拍。只要小规模对得上，大规模递归就敢放心交上去。这套流程，比反复读题解有用得多。
