Давайте представим, что у нас есть матрица битов (которая содержит хотя бы один 1):

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

Мы хотим установить некоторые из битов в этой матрице так, чтобы она образовывала непрерывный двоичный объект 1s, в котором каждый 1прямо или косвенно связан друг с другом 1посредством ортогонального движения:

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с помощью функции поиска в браузере.)

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

Задание

Учитывая матрицу (или массив массивов) битов или логических значений, вернуть минимальное число битов, которое необходимо установить для создания непрерывного континента 1s. Должна существовать возможность перехода от одного установленного бита в матрице к другому только путем перемещения в ортогональном направлении к другим установленным битам.

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

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

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

C (gcc), 308 306 байт

Функция fполучает (height, width, flattened array, pointer to ans)и возвращает ответ по указателю.

Если нет 1в матрице, он вернется 0.

#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;}

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

Ungolfed:

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;
}

Python 2 , 611 байт

Полная программа, которая принимает список списков через пользовательский ввод. Функции Iи dподсчитать количество островов в массиве. Цикл for в конце перечисляет все возможности, где вы можете изменить 0s на 1s, тогда, если остался один островок, хранится число 1s, добавленных в список C. Минимум этого списка - это минимальное количество битовых переключений, необходимых для соединения любых островков. Это очень медленный алгоритм, поэтому он не запускает тестовые наборы, представленные менее чем за 60 секунд (я не пробовал больше), но я пробовал несколько меньших (~ 5x5) тестовых примеров, и похоже, что он работает правильно. Я получил алгоритм подсчета островов с этой страницы.

from itertools import*
def d(g,i,j,v):
 v[i][j],R,C=1,[-1,1,0,0],[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]]<1and 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,c=[w*[0]for r in g],0
 for i in range(len(g)*w):
	if v[i/w][i%w]<1and g[i/w][i%w]>0:v=d(g,i/w,i%w,v);c+=1
 return c           
g=input()
C=[]
for p in [list(t)for t in product([0,1],repeat=sum(r.count(0)for r in g))]:
 h,G,x=0,[r[:]for r in g],len(g[0])
 for i in range(x*len(G)):
	if G[i/x][i%x]<1:h+=p[0];G[i/x][i%x]=p[0];del p[0]
 if I(G)<2:
	C.append(h)
print min(C)

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

Предварительная версия, прежде чем я оптимизировал несколько вещей:

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)