Учитывая черно-белое изображение с белым фоном и набором черных точек, закрасьте набор белых пикселей красным, чтобы между каждой парой черных пикселей был путь.
Детали
Путь - это набор связанных пикселей (8-соседняя связь). Черные пиксели могут использоваться как часть контуров. Цель состоит в том, чтобы минимизировать набор красных пикселей при указанных выше условиях и вывести соответствующее изображение.
Вам не нужно находить оптимальное решение.
Тривиальное и в то же время худшее решение - просто покрасить все белые пиксели в красный.
Пример (пиксели увеличены для наглядности):
Детали
- Для данного пиксельного изображения (в любом подходящем формате) вернуть другое изображение с точками, соединенными, как указано выше, а также целое число, указывающее, сколько было использовано красного пикселя.
- Оценка является произведением (1 + количество красных пикселей) для каждого из 14 тестовых случаев.
- Цель - набрать наименьшее количество очков.
Testcases
14 тестовых случаев показаны ниже. Программа Python для проверки связности выходов может быть найдена здесь.
Мета
Спасибо @Veskah, @Fatalize, @wizzwizz4 и @trichoplax за различные предложения.
Ответы:
С, оценка 2,397х10 ^ 38
Человек это заняло слишком много времени, скорее всего из-за моего выбора языка. Я получил алгоритм, работающий довольно рано, но столкнулся с множеством проблем с выделением памяти (не мог рекурсивно освободить материал из-за переполнения стека, размер утечки был огромен).
Все еще! Он превосходит другую запись в каждом тестовом примере и,
возможно, даже будет оптимальным,получая довольно близкие или точно оптимальные решения большую часть времени.Во всяком случае, вот код:
Проверено на: Arch Linux, GCC 9.1.0,
-O3
Этот код принимает ввод / вывод в пользовательском файле, который я называю «cppm» (потому что он похож на сжатую версию классического формата PPM). Сценарий Python для преобразования в / из него приведен ниже:
Объяснение алгоритма
Этот алгоритм работает так, что он начинает с нахождения всех связанных фигур на изображении, включая красные пиксели. Затем он берет первый и расширяет свою границу по одному пикселю за раз, пока не встретит другую форму. Затем он окрашивает все пиксели от касания до исходной формы (используя связанный список, который он создал по пути отслеживания). Наконец, он повторяет процесс, находя все новые созданные фигуры, пока не останется только одна фигура.
Галерея
Тест-кейс 1, 183 пикселяТест-кейс 2, 140 пикселей
Тест-кейс 3, 244 пикселя
Тест-кейс 4, 42 пикселя
Тест-кейс 5, 622 пикселей
Тестовый случай 6, 1 пиксель
Тест-кейс 7, 104 пикселя
Тест-кейс 8, 2286 пикселей
Тест-кейс 9, 22 пикселя
Тест-кейс 10, 31581 пикселей
Тест-кейс 11, 21421 пикселей
Testcase 12, 5465 пикселей
Тест-кейс 13, 4679 пикселей
Testcase 14, 7362 пикселей
источник
Python, 2.62 * 10 ^ 40
Этот алгоритм просто заполняет (BFS) плоскость, начиная с черных частей изображения, где для каждого нового пикселя мы записываем, из какой черной части оно было затоплено. Как только у нас есть два соседних пикселя с разными черными частями в качестве предков, мы в основном объединяем эти две черные части, соединяя их через предков двух соседей, которых мы только что нашли. Теоретически это может быть реализовано в
O(#pixels)
, но чтобы сохранить объем кода на приемлемом уровне, эта реализация немного хуже.Выход
Гол
источник
Python 3:
1.7x10 ^ 421.5x10 ^ 41Использование
Pillow
,numpy
иscipy
.Предполагается, что изображения находятся в
images
папке, расположенной в том же каталоге, что и скрипт.Отказ от ответственности : обработка всех изображений занимает много времени.
Код
объяснение
Простое решение. Мы начинаем с изменения цвета всех белых пикселей на изображении на красный. При этом гарантируется, что все элементы (любой остров чёрных пикселей) связаны.
Затем мы перебираем все пиксели изображения, начиная с верхнего левого угла и двигаясь вправо и вниз. Для каждого красного пикселя, который мы находим, мы меняем его цвет на белый. Если после этого изменения цвета все еще остается только один элемент (элемент теперь является любым островком черного и красного пикселей), мы оставляем пиксель белым и переходим к следующему пикселю. Однако, если после изменения цвета с красного на белое количество элементов больше единицы, мы оставляем пиксель красным и переходим к следующему пикселю.
Обновить
Как можно видеть (и ожидаемо), соединения, полученные только с использованием этого метода, показывают регулярную структуру, и в некоторых случаях, например на 6-м и 11-м изображениях, появляются ненужные красные пиксели.
Эти лишние красные пиксели можно легко удалить, выполнив итерацию снова над изображением и выполнив те же операции, как описано выше, но из нижнего правого угла в верхний левый угол. Этот второй проход намного быстрее, так как количество красных пикселей, которые должны быть проверены.
Результаты
Изображения, которые были изменены после второго прохода, перечислены дважды, чтобы показать различия.
Количество красных пикселей: 18825
Количество красных пикселей: 334
Количество красных пикселей: 1352
Количество красных пикселей: 20214
Количество красных пикселей: 47268
Количество красных пикселей:
6327Количество красных пикселей: 17889
Количество красных пикселей: 259
Количество красных пикселей: 6746
Количество красных пикселей: 586
Количество красных пикселей:
91Количество красных пикселей: 126
Количество красных пикселей: 212
Количество красных пикселей: 683
Расчет баллов:
(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1,7x10 ^ 42
Обновлен расчет счета после добавления второго прохода:
(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1,5x10 ^ 41
источник