Одинокие острова

10

Входные данные:

2D-массив, содержащий два разных (необязательных) значения. Я буду использовать 0 и 1 при объяснении правил. Формат ввода, конечно, гибкий.


Вызов:

Нули - это вода, а одни - острова. Чтобы обеспечить одиночество, ваша задача - окружить все острова водой, вставив ряды и столбцы нулей. Вы не хотите тратить воду, поэтому вы должны минимизировать количество добавленной воды. Если существует более одного раствора, требующего одинакового количества воды, вам следует добавлять столбцы воды, а не ряды. Я покажу это в тестовых случаях.


Вывод:

Новый, модифицированный 2D массив. Формат вывода, конечно, гибкий.


Тестовые случаи:

Вход и выход разделены тире. Добавленные нули показаны жирным шрифтом. Используйте один из ответов здесь, если вы хотите преобразовать контрольные примеры в более удобные форматы.

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

Обратите внимание, что мы добавили столбец нулей, а не ряд нулей. Это связано с тем, что количество необходимых нулей равно и столбцы должны быть предпочтительными.


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

Обратите внимание, что мы добавили строки, а не столбцы, поскольку для этого требуется наименьшее количество дополнительных нулей.


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

Это потребовало как столбцы, так и строки.


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

Лучше добавить две колонки, чем одну строку, так как для этого требуется меньше воды.


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

Лучше добавить две строки, чем один столбец, так как для этого требуется меньше воды.

Стьюи Гриффин
источник
Относящиеся .
Стьюи Гриффин
Черт, Стьюи, теперь у меня снова в голове застрял «Джек Воробей»!
Лохматый
Эта проблема эквивалентна проблеме покрытия вершин на двудольном графе, и согласно Википедии она может быть решена за полиномиальное время.
user202729
Я передумал ... это может быть взвешено. Во всяком случае для достаточно большой квадратной матрицы это (надеюсь) эквивалентно. Поэтому, если ваш алгоритм «слишком прост», будьте осторожны .
user202729
Я думаю, что у меня есть алгоритм полиномиального времени.
user202729

Ответы:

2

Желе , 37 байт

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

Попробуйте онлайн!

Функция, возвращающая двумерный массив целых чисел. Обратите внимание, что, естественно, в Jelly singleton list отображается как его значение, поэтому Gон используется для форматирования вывода.


  • Ссылка 1: Возврат (срок действия).
  • Ссылка 2: Основная программа.

Программа работает за экспоненциальное время, но до сих пор я не мог придумать ни одного алгоритма полиномиального времени. Использует Ƥна двоичной функции, эта особенность отодвигает вызов.

user202729
источник
2

Python 2 , 374 346 340 339 323 317 байт

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]

Попробуйте онлайн!

TFeld
источник
Я думаю, что первый [:]может быть удален, не влияя на вывод.
user202729
@ user202729, спасибо, думаю можно. Тем не менее, я изменил его :)
TFeld