Codegolf - Make A Bit Continent

Представим, что у нас есть матрица битов (содержащая хотя бы один

 
 
 0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
=> 6

1 0 0 0 0 0 1 0 0
1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0
=> 4

0 0 0 1 1 1 0 1 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 1 1 1 0
1 1 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 1 1 0 0 0 0 0
1 1 1 0 0 1 1 1 0
1 1 1 0 1 1 0 1 1
0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0
0 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 1
=> 8

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
=> 0
 
 
 

Мы хотим установить некоторые биты в этой матрице так, чтобы она формировала непрерывный блок из 1 s, in which every 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 прямо или косвенно связано со всеми другими 1 through orthogonal movement:

(Вы можете увидеть это более четко, выполнив поиск 1 with your browser's "find" feature.)

Однако мы также хотим минимизировать количество устанавливаемых битов.

Задача

Учитывая матрицу (или массив массивов) битов или логических значений, верните минимальное количество битов, которое необходимо установить для создания непрерывного континента 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 s. It should be possible to get from one set bit in the matrix to another by only traveling in an orthogonal direction to other set bits.

Это , поэтому побеждает самая короткая действительная отправка (измеренная в байтах).

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

#код-гольф #код-гольф #бинарная-матрица

C (gcc), 308 306 байт

Функция

 
 
 
 from itertools import*
def d(g,i,j,v):

v[i][j]=1

R=[-1,1,0,0]

C=[0,0,-1,1]

for k in range(4):

if len(g)>i+R[k]>=0<=j+C[k]<len(g[0]):

if v[i+R[k]][j+C[k]]<1:

if g[i+R[k]][j+C[k]]:

v=d(g,i+R[k],j+C[k],v)

return v
def I(g):

w=len(g[0])

v=[[0]*w for r in g]

c=0

for i in range(len(g)):

for j in range(w):

if v[i][j]<1and g[i][j]>0:

v=d(g,i,j,v)

c+=1

return c           
g=input()
z=sum(r.count(0)for r in g)
f=[list(t)for t in product('01',repeat=z)]
C=[]
for p in f:

h=0

G=[r[:]for r in g]

x=len(G[0])

for i in range(x*len(G)):

exec('h+=int(p[0]);G[i/x][i%x]=int(p[0]);del p[0]'*(G[i/x][i%x]<1))

if I(G)<2:

C.append(h)
print min(C)
 
 
 
 

Если нет C in the matrix, it will return 1 .

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

Негольфед:

Питон 2, 611 байт

Полноценная программа, которая принимает список списков посредством пользовательского ввода. Функции d and I подсчитайте количество островов в массиве. Цикл for в конце перечисляет все возможности того, что вы можете изменить. N,M,R,C,T,i,*A; // height, width, result, recursion depth s(x,y) { // depth first search: replace all 1 in the same connected component with 2 i=x*M+y; if(!(x<0|y<0|x>=N|y>=M|A[i]^1)) { // check if out of boundary A[i]=2; s(x, y+1),s(x, y-1),s(x+1, y),s(x-1, y); } } g(i) { // enumerate all posible solutions if(C<R) { if(i!=N*M) { g(i+1); // nothing change for this entry if (!A[i]) { // set the entry to 1 C++, A[i]=1; g(i+1); C--, A[i]=0; } } else { T=1; for (i=0; i<N*M && !A[i]; i++); // find first non-zero entry s(i/M, i%M); // replace the connected component for (i=0; i<N*M; i++) { T&=A[i]!=1; // check if no other components A[i]=!!A[i]; // change 2s back to 1 } if (T) R=C; // update answer } } } f(n,m,a,b)int*a,*b;{ R=(N=n)*(M=m), A=a; g(0); *b=R; } s to #define v A[i] N,M,K,R,C,T,i,*A;s(x,y){i=x*M+y;if(!(x<0|y<0|x>=N|y>=M|v^1))v=2,s(x,y+1),s(x,y-1),s(x+1,y),s(x-1,y);}g(i){if(C<R){if(i^K){g(i+1);if(!v)C+=v=1,g(i+1),v=0,C--;}else{T=1;for(i=0;i<K&&!v;i++);s(i/M,i%M);for(i=0;i<K;i++)T&=v^1,v=!!v;if(T)R=C;}}}f(n,m,a,b)int*a,*b;{K=R=(N=n)*(M=m),A=a;g(0);*b=R;} s, то если остался один остров, сохраняет количество 0 s added to the list 1 . Минимум этого списка — это минимальное количество переворотов битов, необходимое для соединения любых островов. Это очень медленный алгоритм, поэтому он не запускает тестовые примеры, заданные менее чем за 60 секунд (дольше я не пробовал), но я попробовал несколько тестовых примеров меньшего размера (~ 5x5), и, похоже, он работает правильно. Алгоритм подсчета островов я получил от этот страница.

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

Версия для игры в гольф до того, как я оптимизировал несколько вещей: