Wejście:

Tablica 2D zawierająca dwie różne (opcjonalne) wartości. Użyję 0 i 1 podczas wyjaśniania zasad. Format wejściowy jest oczywiście elastyczny.

Wyzwanie:

Zera to woda, a te to wyspy. Aby zapewnić samotność, Twoim zadaniem jest otoczyć wszystkie wyspy wodą, wstawiając rzędy i kolumny zer. Nie chcesz marnować wody, więc musisz zminimalizować ilość dodanej wody. Jeśli istnieje więcej niż jedno rozwiązanie, które wymaga takiej samej ilości dodanej wody, należy dodać kolumny wody, a nie wiersze. Pokażę to w przypadkach testowych.

Wynik:

Nowa, zmodyfikowana tablica 2D. Format wyjściowy jest oczywiście elastyczny.

Przypadki testowe:

Wejścia i wyjścia są oddzielone myślnikami. Dodane zera są wytłuszczone. Użyj jednej z odpowiedzi tutaj, jeśli chcesz przekonwertować przypadki testowe na wygodniejsze formaty.

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

Pamiętaj, że dodaliśmy kolumnę zer, a nie rząd zer. Jest tak, ponieważ liczba niezbędnych zer jest równa i kolumny powinny być preferowane.

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

Pamiętaj, że dodaliśmy wiersze, a nie kolumny, ponieważ wymaga to najmniejszej liczby dodatkowych zer.

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

Wymagało to zarówno kolumn, jak i wiersza.

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

Lepiej dodać dwie kolumny niż jeden rząd, ponieważ wymaga mniej wody.

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

Lepiej dodać dwa rzędy niż jedną kolumnę, ponieważ wymaga mniej wody.

Galaretka , 37 bajtów

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

Wypróbuj online!

Funkcja zwracająca tablicę 2D liczb całkowitych. Zauważ, że naturalnie na liście singletonów Jelly wyświetla się jako jej wartość, dlatego Gsłuży do formatowania wyjścia.

• Link 1: Zwrot (ważność).
• Link 2: Program główny.

Program działa w czasie wykładniczym, ale jak dotąd nie mogłem wymyślić żadnego algorytmu czasu wielomianowego. Wykorzystuje Ƥfunkcję dyadyczną, która ta funkcja stanowi wyzwanie po wyzwaniu.

Python 2 , 374 346 340 339 323 317 bajtów

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]

Wypróbuj online!