Задача 287: кодирование Quadtree (простой алгоритм сжатия)
Квадратное кодирование позволяет нам описывать черно-белое изображение 2N × 2N в виде последовательности бит (0 и 1). Эти последовательности следует читать слева направо так: первый бит относится к полному 2N × 2N области; «0» обозначает раздвоение: текущая область 2n × 2n делится на 4 субрегиона размером 2n-1 × 2n-1, следующие биты содержат описание верхнего левого, верхнего правого, нижнего левого и нижнего правого подпунктов -области - в этом порядке; «10» означает, что текущая область содержит только черные пиксели; «11» указывает, что текущая область содержит только белые пиксели. Учитывайте следующее изображение 4 × 4 (цветные метки обозначают места, где может произойти сплит):
Это изображение может быть описано несколькими последовательностями, например: «001010101001011111011010101010», длиной 30 или «0100101111101110» длиной 16, что является минимальной последовательностью для этого изображения.
Для положительного целого N определите DN как изображение 2N × 2N со следующей схемой окраски: пиксель с координатами x = 0, y = 0 соответствует нижнему левому пикселю, если (x - 2N-1) 2 + (y - 2N-1) 2 ≤ 22N-2, тогда пиксель черный, в противном случае пиксель белый. Какова длина минимальной последовательности, описывающей D24?