dmy#46

[R8D] Z形填数

难度普及
时限 1s
空限 512m
分治递归

数据规模： $1 \le n \le 10$ 。

思路

Z 形填数就是经典的 Z 阶曲线（Morton code）。把行号 $r$ 和列号 $c$ （从 $0$ 开始）的二进制位交错排开，就得到这个格子填入的数字（ $0$ 基下标），加 $1$ 即为答案。具体地，第 $k$ 位上 $c$ 的位放进结果的第 $2k$ 位、 $r$ 的位放进第 $2k+1$ 位。

这是因为：每次分形时，列在低位的 $0/1$ 决定左/右（红黄、蓝绿在 $x$ 轴的区分），行在低位的 $0/1$ 决定上/下；先列后行的顺序对应偶数位放 $c$ 、奇数位放 $r$ 。

$2^n \times 2^n$ 共 $2^{2n} \le 2^{20}$ 个格子，每个格子的位交错是 $O(n)$ 。

复杂度：时间 $O(4^n \cdot n)$ ，空间 $O(1)$ （直接用 println 输出）。

仓颉实现

查看仓颉实现

import std.convert.*
import std.env.*

main() {
    let reader = getStdIn()
    let n = Int64.parse(reader.readln().getOrThrow())
    var size: Int64 = 1
    for (_ in 0..n) {
        size *= 2
    }
    let S = size
    for (r in 0..S) {
        for (c in 0..S) {
            var idx: Int64 = 0
            var bit: Int64 = 0
            while (bit < n) {
                idx = idx | (((c >> bit) & 1) << (2 * bit))
                idx = idx | (((r >> bit) & 1) << (2 * bit + 1))
                bit += 1
            }
            print(idx + 1)
            if (c < S - 1) {
                print(" ")
            }
        }
        println()
    }
}

要点：

Z 形分形递归展开后，填入数字正是行列二进制位交错的结果，无需真的递归模拟。