← 完整题目索引

PROJECT EULER · #0287

四叉树编码(一种简单的压缩算法)

Quadtree Encoding (a Simple Compression Algorithm)

仅题目 · 已解决原题 ↗

四叉树编码允许我们将 2N×2N 黑白图像描述为位序列(0 和 1)。这些序列应从左到右读取,如下所示:

  • 第一位处理完整的 2N×2N 区域;
  • "0"表示分割:
    当前 2n×2n 区域被划分为 4 个维度为 2n1×2n1 的子区域,
    接下来的位包含左上角、右上角、左下角和右下角子区域的描述 - 按此顺序;
  • "10"表示当前区域仅包含黑色像素;
  • "11"表示当前区域仅包含白色像素。

考虑以下 4×4 图像(彩色标记表示可能发生分割的位置):

0287_quadtree.gif

该图像可以通过多个序列来描述,例如: "001010101001011111011010101010",长度为 30,或
"0100101111101110",长度为 16,这是该图像的最小序列。

对于正整数 N,将 DN 定义为 2N×2N 图像,并使用以下着色方案:

  • 坐标为 x=0,y=0 的像素对应于左下角像素,
  • 如果 (x2N1)2+(y2N1)222N2 则像素为黑色,
  • 否则像素为白色。

描述D24的最小序列的长度是多少?

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。