Make a Bit Continent
C (gcc), 308 306 bytes

Function f receives (height, width, flattened array, pointer to ans), and returns answer by pointer.

If there's no 1 in the matrix, it will return 0.



#define v A[i]
N,M,K,R,C,T,i,*A;s(x,y){i=x*M+y;if(!(x&lt;0|y&lt;0|x&gt;=N|y&gt;=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&lt;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&lt;K&amp;&amp;!v;i++);s(i/M,i%M);for(i=0;i&lt;K;i++)T&amp;=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;}


Try it online!

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&lt;0|y&lt;0|x&gt;=N|y&gt;=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&lt;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&lt;N*M &amp;&amp; !A[i]; i++); // find first non-zero entry
            s(i/M, i%M);     // replace the connected component
            for (i=0; i&lt;N*M; i++) {
                T&amp;=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;
}