Las islas solitarias

10

Entrada:

Una matriz 2D que contiene dos valores distintos (opcionales). Usaré 0 y 1 cuando explique las reglas. El formato de entrada es, por supuesto, flexible.


Desafío:

Los ceros son agua y los unos son islas. Para garantizar la soledad, su tarea es rodear todas las islas con agua insertando filas y columnas de ceros. No desea desperdiciar agua, por lo que debe minimizar la cantidad de agua agregada. En caso de que haya más de una solución que requiera la misma cantidad de agua agregada, entonces debe agregar columnas de agua, no filas. Mostraré esto en los casos de prueba.


Salida:

La nueva matriz 2D modificada. El formato de salida es, por supuesto, flexible.


Casos de prueba:

La entrada y la salida están separadas por guiones. Los ceros agregados se muestran en negrita. Utilice una de las respuestas aquí si desea convertir los casos de prueba a formatos más convenientes.

1
---
1

1 1
---
1 0 1

1 1
1 1
---
1 0 1
0 0 0
1 0 1

1 0
0 1
---
1 0 0
0 0 1

Tenga en cuenta que agregamos una columna de ceros, no una fila de ceros. Esto se debe a que el número de ceros necesarios es igual y se deben preferir las columnas.


1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
---
1 0 0 0 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 1 0

Tenga en cuenta que agregamos filas, no columnas, ya que eso requiere la menor cantidad de ceros adicionales.


0 0 1 0 0
0 1 1 1 0
---
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0

Esto requería tanto columnas como una fila.


0 0 1 0 0
0 1 0 1 0
---
0 0 0 1 0 0 0
0 1 0 0 0 1 0

Es mejor agregar dos columnas que una fila, ya que requiere menos agua.


0 0
1 0
0 1
1 0
0 0
---
0 0 
1 0
0 0 
0 1 
0 0 
1 0
0 0

Es mejor agregar dos filas que una columna, ya que requiere menos agua.

Stewie Griffin
fuente
Relacionados .
Stewie Griffin
Maldita sea, Stewie, ¡ahora tengo a "Jack Sparrow" atrapado en mi cabeza otra vez!
Shaggy
Este problema es equivalente al problema de la cubierta de vértices en el gráfico bipartito, y de acuerdo con Wikipedia, se puede resolver en tiempo polinómico.
user202729
Cambié de opinión ... puede estar ponderado. De todos modos, para una matriz cuadrada suficientemente grande es (con suerte) equivalente. Entonces, si su algoritmo es "demasiado simple", tenga cuidado .
user202729
Creo que tengo un algoritmo de tiempo polinómico.
user202729

Respuestas:

2

Jalea , 37 bytes

ṫƤ-S€ZƊ⁺FỊẠ
Z_,,WƲ€ŒpẎ€Ʋ⁺€ẎLÞFL$ÞṚÇÞṪ

Pruébalo en línea!

Función que devuelve una matriz 2D de enteros. Tenga en cuenta que, naturalmente, en Jelly la lista singleton se muestra como su valor, por lo que Gse utiliza para formatear la salida.


  • Enlace 1: Devolución (validez).
  • Enlace 2: Programa principal.

El programa se ejecuta en tiempo exponencial, pero hasta ahora no se me ocurrió ningún algoritmo de tiempo polinómico. Usos Ƥen la función diádica, esa característica es posterior al desafío.

usuario202729
fuente
2

Python 2 , 374 346 340 339 323 317 bytes

R=range;L=len
def f(a):
 w,h=L(a[0]),L(a);W=[]
 for i in R(2**w):
	A=zip(*a)
	for c in R(w):A[-c:-c]=[[0]*h]*(i&1<<c>0)
	for j in R(2**h):
	 B=zip(*A);x=L(B[0])
	 for r in R(h):B[-r:-r]=[(0,)*x]*(j&1<<r>0)
	 y=L(B);W+=[(w*h-x*y,x,B)]*all(sum(B[i][j:j+2]+B[i+1][j:j+2])<2for i in R(y-1)for j in R(x))
 return max(W)[2]

Pruébalo en línea!

TFeld
fuente
Creo que el primero [:]se puede eliminar sin afectar la salida.
usuario202729
@ user202729, gracias, creo que puede. Mientras tanto
cambié