Dada una imagen en blanco y negro con un fondo blanco y un conjunto de puntos negros, pinte un conjunto de píxeles blancos en rojo, de modo que haya un camino entre cada par de píxeles negros.
Detalles
Una ruta es un conjunto de píxeles conectados (conectividad de 8 vecindades). Los píxeles negros se pueden usar como parte de las rutas. El objetivo es tratar de minimizar el conjunto de píxeles rojos en las condiciones anteriores y generar una imagen correspondiente.
No tiene que encontrar la solución óptima.
Una solución trivial y al mismo tiempo peor es pintar todos los píxeles blancos en rojo.
Ejemplo (los píxeles se amplían para mayor visibilidad):
Detalles
- Dada una imagen de píxeles (en cualquier formato adecuado), devuelve otra imagen con los puntos conectados como se especifica anteriormente, así como un número entero que indica cuántos píxeles rojos se usaron.
- La puntuación es el producto de (1 + el número de píxeles rojos) para cada una de las 14 cajas de prueba.
- El objetivo es tener el puntaje más bajo.
Casos de prueba
Las 14 cajas de prueba se muestran a continuación. Aquí se puede encontrar un programa de Python para verificar la conexión de las salidas .
Meta
Gracias a @Veskah, @Fatalize, @ wizzwizz4 y @trichoplax por las diversas sugerencias.
Respuestas:
C, puntaje 2.397x10 ^ 38
Hombre, esto tardó demasiado en hacerlo, probablemente debido a mi elección del idioma. Obtuve el algoritmo funcionando bastante temprano, pero me encontré con muchos problemas con la asignación de memoria (no podía liberar recursivamente cosas debido a desbordamientos de pila, los tamaños de fuga eran enormes).
¡Todavía! Es mejor que la otra entrada en cada caso de prueba, e
incluso puede ser óptimo, seacerca bastante o es exactamente una solución óptima la mayor parte del tiempo.De todos modos, aquí está el código:
Probado en: Arch Linux, GCC 9.1.0,
-O3
Este código toma entrada / salida en un archivo personalizado que llamo "cppm" (porque es como una versión condensada del clásico formato PPM). A continuación se muestra un script de Python para convertir a / desde:
Explicación del algoritmo
El funcionamiento de este algoritmo es que comienza por encontrar todas las formas conectadas en la imagen, incluidos los píxeles rojos. Luego toma el primero y expande su frontera un píxel a la vez hasta que encuentra otra forma. Luego colorea todos los píxeles desde el toque hasta la forma original (usando la lista vinculada que hizo en el camino para realizar un seguimiento). Finalmente, repite el proceso, encontrando todas las nuevas formas creadas, hasta que solo quede una forma.
Galería de imágenes
Caso de prueba 1, 183 píxelesTestcase 2, 140 píxeles
Testcase 3, 244 píxeles
Testcase 4, 42 píxeles
Testcase 5, 622 píxeles
Testcase 6, 1 píxel
Testcase 7, 104 píxeles
Testcase 8, 2286 píxeles
Testcase 9, 22 píxeles
Testcase 10, 31581 píxeles
Testcase 11, 21421 píxeles
Testcase 12, 5465 píxeles
Testcase 13, 4679 píxeles
Testcase 14, 7362 píxeles
fuente
Python, 2.62 * 10 ^ 40
Este algoritmo simplemente inunda (BFS) el plano a partir de las partes negras de la imagen, donde para cada nuevo píxel registramos de qué parte negra se inundó. Tan pronto como tengamos dos píxeles vecinos con diferentes partes negras como ancestros, básicamente fusionamos estas dos partes negras uniéndolos a través de los ancestros de los dos vecinos que acabamos de encontrar. En teoría, esto podría implementarse
O(#pixels)
, pero para mantener la cantidad de código en un nivel aceptable, esta implementación es un poco peor.Salida
Puntuación
fuente
Python 3:
1.7x10 ^ 421.5x10 ^ 41El uso
Pillow
,numpy
yscipy
.Se supone que las imágenes se encuentran en una
images
carpeta ubicada en el mismo directorio que el script.Descargo de responsabilidad : lleva mucho tiempo procesar todas las imágenes.
Código
Explicación
Solución trivial. Comenzamos cambiando el color de todos los píxeles blancos de una imagen a rojo. Al hacer esto, se garantiza que todos los elementos (cualquier isla de píxeles negros) estén conectados.
Luego, iteramos sobre todos los píxeles de la imagen comenzando desde la esquina superior izquierda y moviéndonos hacia la derecha y hacia abajo. Por cada píxel rojo que encontramos cambiamos su color a blanco. Si después de este cambio de color todavía hay un solo elemento (un elemento que ahora es una isla de píxeles negros y rojos), dejamos el píxel blanco y pasamos al siguiente píxel. Sin embargo, si después del cambio de color de rojo a blanco, el número de elementos es mayor que uno, dejamos el píxel rojo y pasamos al siguiente píxel.
Actualizar
Como se puede ver (y esperar), las conexiones obtenidas al usar solo este método muestran un patrón regular y, en algunos casos, como en las imágenes 6 y 11, hay píxeles rojos innecesarios.
Estos píxeles rojos adicionales se pueden eliminar fácilmente iterando nuevamente sobre la imagen y realizando las mismas operaciones que se explicaron anteriormente, pero desde la esquina inferior derecha hasta la esquina superior izquierda. Este segundo paso es mucho más rápido ya que la cantidad de píxeles rojos que se deben verificar.
Resultados
Las imágenes que se modifican después de la segunda pasada se enumeran dos veces para mostrar las diferencias.
Número de píxeles rojos: 18825
Número de píxeles rojos: 334
Número de píxeles rojos: 1352
Número de píxeles rojos: 20214
Número de píxeles rojos: 47268
Número de píxeles rojos:
6327Número de píxeles rojos: 17889
Número de píxeles rojos: 259
Número de píxeles rojos: 6746
Número de píxeles rojos: 586
Número de píxeles rojos:
9 91Número de píxeles rojos: 126
Número de píxeles rojos: 212
Número de píxeles rojos: 683
Cálculo del puntaje:
(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
Cálculo del puntaje actualizado después de agregar el segundo pase:
(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
fuente