Максимальное количество определенной последовательности элементов в 3D-массиве

Question

Итак, для назначения структур данных мне пришлось инициализировать каждый элемент в статически распределенной 3D-матрице с одним из пяти выбранных цветов. Массив был типа ColorEnum, который был объявлен как это:

---

перечисление ColorEnum {красный, оранжевый, желтый, зеленый, синий};

---

Моя задача состояла в том, чтобы найти индексы элементов, которые составляют определенную последовательность элементов (что означает каждый элемент в последовательности логически прикасаясь к следующему элементу последовательности либо стороны в сторону, сверху вниз , или спереди назад). Полная последовательность будет такой, в которой элемент RED будет касаться элемента ORANGE, который касается элемента ЖЕЛТЫЙ, который касается элемента GREEN, касающегося BLUE-элемента. Чтобы прикоснуться, вся сторона обоих элементов должна быть смежной, а не только край или угол. Таким образом, каждый элемент может касаться максимум 6 других элементов. Отдельный элемент может использоваться более чем в одной последовательности. Чтобы сохранить индексы элементов в последовательности, я использовал статически выделенный 1D массив структур, который будет содержать индексы строки, столбца и глубины элемента. Чтобы сохранить каждую последовательность, я использовал еще один статически выделенный 1D массив массивов, которые содержат индексы элементов в последовательности. Переходя к моему вопросу, чтобы использовать как можно меньше памяти, мне нужно знать, какой размер выделяется массиву массивов. Я бы хотел, чтобы этот размер был равен максимальному числу этих КРАСНЫХ, ОРАНЖЕВЫХ, ЖЕЛТЫХ, ЗЕЛЕНЫХ, СИНИЙ последовательностей, но я не знаю, как определить это число. Любые математики-гении, которые там заботятся, чтобы дать мне руку? Моя задача давно закончена. У меня есть 94/100, но этот вопрос меня беспокоит. Я ценю помощь.

Answer 1

Максимальное количество возможных последовательностей будет зависеть от размеров вашего 3D-массива и (конечно) заполнения сетки. Взглянув на него с комбинаторного угла, я попытался бы найти наиболее эффективное заполнение такой 3D-сетки. Однако выделение максимума предполагает худший случай, и вам будет лучше с векторами, как прокомментировал @Kevin.

Одно заполнение сетки, которая кажется мне эффективной, состоит в том, чтобы заполнить 6 смежных положений 1 блока тремя предыдущими цветами и тремя его следующими цветами (так что желтый блок будет иметь 3 оранжевых и 3 зеленых блока, как соседи). Если вы заполняете соседние соседи (назад, вправо, вверх) следующим цветом и (передним, левым, нижним) соседями с предыдущим цветом, то возникающая структура позволяет использовать один блок во множестве последовательностей. Если цвет не имеет следующего/предыдущего цвета, только предыдущий/следующий цвет.

В 2D вы бы иметь что-то вроде этого (сокращенные colornames)

BGYOROYGBGYOROYGB 
GBGYOROYGBGYOROYG 
YGBGYOROYGBGYOROY 
OYGBGYOROYGBGYORO 
ROYGBGYOROYGBGYOR 

количество последовательностей, используя нижний левый R является 2^4, то количество последовательностей, используя один из среднего R (в бесконечное поле) 2^5. Точный полный nr последовательностей в трехмерном поле может быть затем рассчитан для этого шаблона с учетом границ (и, возможно, другой схемы на краях, так как будет некоторая потеря)

Мой метод заполнения - это всего лишь один способ заполнение сетки, возможны и другие возможности.