Find minimum number 1's so the matrix consist of 1 connected region of 1's

Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ can reach another one through a sequence of neighbors.

Example:

100
000
001

Here we need 3 $1$'s:

100
100
111

How can we efficiently find the minimum number of $1$'s to add, and where?

If you model your problem with graphs, Your problem is like Steiner Tree problem:

See here for simplest possible definition.


Given a weighted graph in which a subset of vertices are identified as
terminals, find a minimum-weight connected subgraph that includes all
the terminals.

As you can see it's NPC in general, but in your case your graph is grid graph, may be you can find good solution for it, but for your current example (when terminals are in boundary) you can see Steiner tree in grid graphs paper.

Anyway there are excellent heuristics for Steiner Tree problem, you can apply similar approach to your problem.

P.S: You can assume neighbor 1s are connected nodes, after that you can contract their edges to make a new graph, your new created graph is planar, and if you could solve the Steiner Tree for it you can solve your problem, but may be there is a good solution for your problem which is independent from Steiner Tree.

StackExchange Computer Science Q#1301, answer score: 5