As Ilhas Solitárias

10

Entrada:

Uma matriz 2D contendo dois valores distintos (opcionais). Usarei 0 e 1 ao explicar as regras. O formato de entrada é obviamente flexível.


Desafio:

Zeros são água e uns são ilhas. Para garantir a solidão, sua tarefa é cercar todas as ilhas com água, inserindo linhas e colunas de zeros. Você não quer desperdiçar água, por isso deve minimizar a quantidade de água adicionada. Caso haja mais de uma solução que exija a mesma quantidade de água adicionada, adicione colunas de água, não linhas. Vou mostrar isso nos casos de teste.


Resultado:

A nova matriz 2D modificada. O formato de saída é obviamente flexível.


Casos de teste:

Entrada e saída são separadas por traços. Os zeros adicionados são mostrados em negrito. Use uma das respostas aqui se desejar converter os casos de teste para formatos mais 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

Observe que adicionamos uma coluna de zeros, não uma linha de zeros. Isso ocorre porque o número de zeros necessários é igual e as colunas devem ser preferidas.


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

Observe que adicionamos linhas, não colunas, pois isso requer a menor quantidade de zeros extras.


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

Isso exigiu colunas e uma linha.


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

Melhor adicionar duas colunas do que uma linha, pois requer menos água.


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

Melhor adicionar duas linhas do que uma coluna, pois requer menos água.

Stewie Griffin
fonte
Relacionado .
Stewie Griffin
Droga, Stewie, agora eu tenho "Jack Sparrow" preso na minha cabeça de novo!
Shaggy
Esse problema é equivalente ao problema de cobertura de vértices no gráfico bipartido e, de acordo com a Wikipedia , pode ser resolvido em tempo polinomial.
usar o seguinte comando
Eu mudei de idéia ... pode ser pesado. De qualquer forma, para uma matriz quadrada suficientemente grande, é (espero) equivalente. Portanto, se o seu algoritmo for "muito simples", tenha cuidado .
usar o seguinte comando
Eu acho que tenho um algoritmo de tempo polinomial.
precisa saber é o seguinte

Respostas:

2

Geléia , 37 bytes

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

Experimente online!

Função retornando uma matriz 2D de números inteiros. Observe que, naturalmente, na lista de singleton Jelly é exibido como seu valor, então Gé usado para formatar a saída.


  • Link 1: Retorno (validade).
  • Link 2: Programa principal.

O programa é executado em tempo exponencial, mas até agora eu não conseguia pensar em nenhum algoritmo de tempo polinomial. Usa Ƥna função diádica, esse recurso pós-data do desafio.

user202729
fonte
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]

Experimente online!

TFeld
fonte
Eu acho que o primeiro [:]pode ser removido sem afetar a saída.
usar o seguinte comando
@ user202729, Obrigado, acho que pode. Eu tinha mudado, entretanto embora :)
TFeld