Imaginemos que tenemos una matriz de bits (que contiene al menos uno 1
):
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
Queremos establecer algunos de los bits en esta matriz de modo que forme una gota contigua de 1
s, en la que cada uno 1
esté conectado directa o indirectamente entre sí a 1
través del movimiento ortogonal:
0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1 0 1 0
1 1 0 0 1 0 0 1 1 1 1
0 0 0 1 1 1 1 0 0 1 0
(Puede ver esto más claramente si busca 1
con la función "buscar" de su navegador).
Sin embargo, también queremos minimizar la cantidad de bits que establecemos.
La tarea
Dada una matriz (o matriz de matrices) de bits o booleanos, devuelve el número mínimo de bits que deben establecerse para crear un continente contiguo de 1
s. Debería ser posible pasar de un bit establecido en la matriz a otro solo viajando en una dirección ortogonal a otros bits establecidos.
Este es el código de golf , por lo que gana el envío válido más corto (medido en bytes).
Casos de prueba
0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
=> 6
1 0 0 0 0 0 1 0 0
1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0
=> 4
0 0 0 1 1 1 0 1 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 1 1 1 0
1 1 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 1 1 0 0 0 0 0
1 1 1 0 0 1 1 1 0
1 1 1 0 1 1 0 1 1
0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0
0 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 1
=> 8
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
=> 0
fuente
1
en la matriz?Respuestas:
C (gcc),
308306 bytesLa función
f
recibe(height, width, flattened array, pointer to ans)
y devuelve la respuesta por puntero.Si no hay
1
en la matriz, volverá0
.Pruébalo en línea!
Sin golf:
fuente
Python 2 , 611 bytes
Un programa completo que toma una lista de listas a través de la entrada del usuario. Las funciones
I
yd
cuentan el número de islas en la matriz. El bucle for al final enumera todas las posibilidades de dónde puede cambiar0
s a1
s y, si queda una isla, almacena el número de1
s agregados a la listaC
. El mínimo de esa lista es el número mínimo de cambios de bits necesarios para conectar cualquier isla. Es un algoritmo muy lento, por lo que no ejecuta los casos de prueba dados en menores de 60 años (no lo intenté más) pero probé algunos casos de prueba más pequeños (~ 5x5) y parece estar funcionando correctamente. Obtuve el algoritmo de conteo de islas de esta página.Pruébalo en línea!
Versión pregolfed antes de optimizar algunas cosas:
fuente