Задача 287
Кодирование квадрадерева (простой алгоритм сжатия)

Кодирование квадрадерева позволяет нам представить черно-белое изображение размерами 2^(N)×2^(N в виде последовательности битов (0 и 1). Такие последовательностисчитываются слева направо следующим образом:

  • первый бит относится ко всему блоку размерами 2^(N)×2^(N;
  • "0" используется в качестве разделителя:
    обрабатываемый блок размерами 2^(n)×2^(n делится на 4 подблока размерами 2^(n-1)×2^(n-1) каждый,
    а последующие биты описывают верхний левый, верхний правый, нижний левый и нижний правый под-блоки -причем, именно в указанном порядке;
  • "10" указывает на то, что текущий блок содержит только черныепиксели;
  • "11" указывает на то, что текущий блок содержит только белые пиксели.

Рассмотрим следующее изображение размерами 4×4 (цветными отметкамиуказаны места, в которых можно осуществить деление на подблоки):

Это изображение можно описать различными последовательностями, к примеру:
"001010101001011111011010101010",длиною 30 символов, или же
"0100101111101110",длиною 16 символов, и это - самая короткая возможная последовательность для заданного изображения.

Для положительного целого числа N определим D_(N), как изображение размерами 2^(N)×2^(N со следующей цветовой палитрой:

  • пиксель с координатами x = 0, y = 0соответствует самому нижнеми левому пикселю,
  • если (x - 2^(N-1))^(2) + (y - 2^(N-1))^(2) ≤ 2^(2N-2) топиксель окрашен в черный цвет,
  • в противном случае пиксель окрашен в белый цвет.

Какова длина самой короткой последовательности, описывающей изображение D_(24) ?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net