Let's imagine we have a matrix of bits (which contains at least one 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
We want to set some of the bits in this matrix such that it forms a contiguous blob of 1
s, in which every 1
is directly or indirectly connected to every other 1
through orthogonal movement:
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
(You can see this more clearly by searching for 1
with your browser's "find" feature.)
However, we also want to minimize the number of bits that we set.
The Task
Given a matrix (or array of arrays) of bits or booleans, return the minimum number of bits that need to be set to create a contiguous continent of 1
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.
This is code-golf, so the shortest valid submission (measured in bytes) wins.
Test Cases
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
in the matrix? \$\endgroup\$