На восемнадцатый день Advent of Code мы работаем с вокселями, чтобы рассчитать поверхность капель лавы. Я призываю вас сначала попробовать решить ее самостоятельно https://adventofcode.com.
Вход
Наш вход сегодня представляет собой серию кубиков. Мы создадим пользовательский тип для представления куба и примем входные данные как std::vector<Cube>.
Подсчет непокрытых сторон
В первой части нам нужно подсчитать общее количество сторон наших вокселей лавы, которые не покрыты другими вокселями.
Так как мы работаем с небольшим количеством кубов, мы можем выполнить полный перебор, перебирая соседей каждого куба и проверяя, существует ли такой куб в наших входных данных.
Если такого куба нет, то эта сторона куба не покрыта, и наоборот.
Игнорирование внутренних карманов
Часть вторая добавляет значительное осложнение. Нам нужно только посчитать стороны, соприкасающиеся с внешним пространством, и игнорировать внутренние карманы.
К счастью, мы работаем с небольшим количеством кубов и небольшим пространством (19x19x19 для моего ввода). Следовательно, мы можем использовать полный перебор (исследуя внешнее пространство) и подсчитывать стороны кубов, с которыми мы сталкиваемся.
Мы будем искать в пространстве на один куб больше в каждом измерении (21x21x21 для моего ввода), начиная с одного из углов, используя поиск в ширину.
Ссылки
Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.
Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.
