group-telegram.com/Pyroborea/16668
Last Update:
#advent_of_code_2024
Day 12
https://adventofcode.com/2024/day/12
Part 1
Задача на розфарбування графа.
Запускаємо функцію, яка розфарбовує матрицю по суміжним клітинкам.
Помітимо, що периметр можна знайти за кількістю вершин та їх сусідів в розфарбованому графі (периметр = 4 * кількість - кількість сусідів).
Легко рахуємо суму цін, яка є множенням периметра на площу (кількість вершин).
Part 2
Тепер замість периметру треба враховувати кількість сторін многокутника.
Для цього будемо акумулювати не сусідів вершини, а кількість вертикальних і горизонтальних сторін.
Розпочнемо для горизонтальних: будемо проходити масив зліва-направо зверху-вниз.
Для кожної вершини матриці будемо перевіряти її верхню та нижню грань, для них будемо записувати теперішній колір грані. Наприклад, якщо колір грані не міняється, то це означає, що нам не треба додавати ще одну сторону, бо вона продовжується. Але якщо колір грані помінявся, то це означає, що між двома вершинами була поставлена грань (тобто огорожа по задачі). Також варто враховувати, чи співпадає колір двох вершин - якщо так, то грані між ними немає: це внутрішня частина многокутника.
Робимо те ж саме відповідно для лівої та правої грані вершини матриці, по неї будемо проходитись зверху-вниз зліва-направо.
Сумуємо кількості сторін, маємо ціну і маємо результат.
солюшн тут: https://github.com/Pyroarsonist/advent-of-code-2024
BY спірітус маргіналіс
Share with your friend now:
group-telegram.com/Pyroborea/16668