做算法题最怕遇到这种题看起来像几何实际考的是递归你以为要画图模拟结果二维数组连一角的零头都开不下。《算法竞赛进阶指南》递推与递归章节里那道“分形之城”我第一次见时盯着题面愣了半天后来才发现整道题就是一道“用递归把编号翻译成坐标”的模板题。分形结构、旋转翻转、编号映射、欧氏距离一招拆开其实特别清爽。这篇文章就把这道题的完整拆解、坐标变换推导、代码实现和踩坑记录一次讲透不管你是刚接触递归、还是准备参加算法竞赛都应该能把题解看懂并复现出来。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 ≤ 31A、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 加 leny 也加 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 的坐标。n2len2cnt4。m5block5/41rest5%41说明它在右上子块。递归求 calc(1, 1)得到等级 1 中编号 1 的坐标。等级 1 中编号 1 是 (0, 1)。右上块变换(0, 12) (0, 3)。所以编号 5 在等级 2 的坐标是 (0, 3)。再求编号 13。n2m13block3rest1说明它在左下子块。递归求 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 城市中编号 m0 起始的坐标 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 最大 312 * n - 2 最大是 601LL 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。递归深度方面n31 最多向下递归 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 的暴力生成程序用它输出每个编号的坐标再和递归函数的结果对拍。只要小规模对得上大规模递归就敢放心交上去。这套流程比反复读题解有用得多。