Die einsamen Inseln

10

Eingang:

Ein 2D-Array mit zwei unterschiedlichen (optionalen) Werten. Ich werde 0 und 1 verwenden, wenn ich die Regeln erkläre. Das Eingabeformat ist natürlich flexibel.


Herausforderung:

Nullen sind Wasser und eins sind Inseln. Um die Einsamkeit zu gewährleisten, müssen Sie alle Inseln mit Wasser umgeben, indem Sie Zeilen und Spalten mit Nullen einfügen. Sie möchten kein Wasser verschwenden, daher müssen Sie die Menge des hinzugefügten Wassers minimieren. Wenn es mehr als eine Lösung gibt, für die dieselbe Menge Wasser hinzugefügt werden muss, sollten Sie Wasserspalten und keine Zeilen hinzufügen. Ich werde dies in den Testfällen zeigen.


Ausgabe:

Das neue, modifizierte 2D-Array. Das Ausgabeformat ist natürlich flexibel.


Testfälle:

Eingabe und Ausgabe werden durch Bindestriche getrennt. Hinzugefügte Nullen werden in Fettdruck angezeigt. Verwenden Sie hier eine der Antworten , wenn Sie die Testfälle in bequemere Formate konvertieren möchten.

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

Beachten Sie, dass wir eine Spalte mit Nullen hinzugefügt haben, keine Zeile mit Nullen. Dies liegt daran, dass die Anzahl der erforderlichen Nullen gleich ist und Spalten bevorzugt werden sollten.


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

Beachten Sie, dass wir Zeilen und keine Spalten hinzugefügt haben, da dies die geringste Anzahl zusätzlicher Nullen erfordert.


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

Dies erforderte sowohl Spalten als auch eine Zeile.


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 ist besser, zwei Spalten als eine Zeile hinzuzufügen, da weniger Wasser benötigt wird.


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 ist besser, zwei Zeilen als eine Spalte hinzuzufügen, da weniger Wasser benötigt wird.

Stewie Griffin
quelle
Verwandte .
Stewie Griffin
Verdammt, Stewie, jetzt habe ich wieder "Jack Sparrow" im Kopf!
Shaggy
Dieses Problem entspricht dem Vertex-Cover-Problem in einem zweigeteilten Graphen und kann laut Wikipedia in Polynomzeit gelöst werden.
user202729
Ich habe es mir anders überlegt ... es könnte gewichtet sein. Auf jeden Fall ist es für eine ausreichend große quadratische Matrix (hoffentlich) äquivalent. Wenn Ihr Algorithmus also "zu einfach" ist, seien Sie vorsichtig .
user202729
Ich glaube, ich habe einen Polynomzeitalgorithmus.
user202729

Antworten:

2

Gelee , 37 Bytes

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

Probieren Sie es online aus!

Funktion, die ein 2D-Array von Ganzzahlen zurückgibt. Beachten Sie, dass natürlich in Jelly Singleton-Liste als Wert so angezeigt wirdG die Ausgabe formatiert wird.


  • Link 1: Rückgabe (Gültigkeit).
  • Link 2: Hauptprogramm.

Das Programm läuft in exponentieller Zeit, aber bisher konnte ich mir keinen polynomiellen Zeitalgorithmus vorstellen. Verwendet die Ƥdyadische Funktion, die die Herausforderung nachdatiert.

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

Probieren Sie es online aus!

TFeld
quelle
Ich denke, der erste [:]kann entfernt werden, ohne die Ausgabe zu beeinflussen.
user202729
@ user202729, Danke, ich denke es kann. Ich hatte es in der Zwischenzeit geändert :)
TFeld