Идет девятый день Пришествия кода. Сегодня мы проанализируем 2D-матрицу на наличие низких точек и непрерывных областей.

Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.

День 9: Часть 1

Наши входные данные представляют собой карту высот со значениями от 0 до 9, представляющими высоту. Наша первая задача — найти низкие точки на карте. Нижняя точка — это точка, окруженная со всех четырех сторон более высокими значениями. Мы также считаем точки за пределами карты как высоту девять.

Нам нужна функция для чтения ввода, и затем я решил предоставить тестовую функцию, ожидая, что основная функция будет перебирать карту:

Для быстрого теста используем данные из AoC:

После этого мы можем реализовать наши две функции. Поскольку каждый элемент представляет собой одну цифру, сегодня мы будем разбирать входной символ за символом:

Обратите внимание: поскольку мы заинтересованы в обнаружении символов новой строки, мы должны отключить std::ios_base::skipws. По умолчанию чтение символа пропускает пробелы. Здесь я решил использовать emplace_back, поэтому давайте обсудим разницу с push_back. Здесь:

  • мы читаем строку, и вектор строки будет перераспределяться по мере необходимости
  • с emplace_back и перемещением вектора, он передает свой выделенный буфер вновь созданному вектору внутри результата
  • чтение следующей строки приведет к другому распределению

Если бы вместо этого мы использовали push_back:

  • при чтении первой строки вектор будет перераспределяться по мере необходимости
  • с push_back внутренний буфер будет копироваться во вновь созданный вектор внутри результата
  • мы бы явно вызвали clear(), чтобы удалить данные из предыдущей строки, что не меняет пропускную способность

Наконец, чтобы проверить, является ли конкретная точка на карте высот нижней точкой, нам нужно проверить четырех соседей с учетом граничных условий.

Затем внутри основной функции мы перебираем все точки карты и проверяем, являются ли они нижними точками:

День 9: Часть 2

В части 2 мы должны найти три самых больших бассейна, где бассейн — это просто связанная область высот меньше 9. Следовательно, мы можем переформулировать задачу и считать высоту девять стеной, а все остальное — «пустой» областью. При этом все, что нам нужно сделать, это поиск с заполнением / поиском в ширину. Более того, нас волнует только размер бассейнов, поэтому мы можем использовать деструктивный подход, просто меняя каждую посещаемую точку на карте на стену (девять).

Для тестирования мы полагаемся на данные тестирования из AoC:

Для нашей части очереди поиска в ширину мы используем std::queue, но вы также можете использовать std::deque или даже std::unordered_set (что немного упростит код, но повлияет на производительность).

Обновление карты и увеличение размера можно исключить до проверки направления; однако потенциально мы могли бы посетить каждую координату до четырех раз.

В нашей основной функции мы снова перебираем карту, вызывая flood_fill, когда сталкиваемся с потенциальным бассейном (не стеной):

Для хранения размеров у нас есть несколько вариантов в зависимости от того, есть ли у нас проблемы с памятью или производительностью. Использование вектора и сортировки является наиболее простым подходом, но он также требует затрат памяти O(n) на хранение всех размеров бассейнов и затрат O(n*logn) на сортировку всех размеров в конце.

В качестве альтернативы мы могли бы:

  • используйте три переменные и немного логики обновления
  • используйте std::priority_queue и сохраните в нем только три элемента
  • используйте std::set с той же идеей, что и priority_queue

Ссылки и технические примечания

Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.

Посмотрите в этом списке статьи о других днях появления кода.

И, пожалуйста, не забудьте попробовать Пришествие кода на себе.

Спасибо за чтение

Спасибо, что прочитали эту статью. Вам понравилось?

Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.