Riddle: How to change matrix color?

algorithm, graph, language-agnostic, matrix

Solution

You proposed the solution:

It looks like a graph problem. The matrix elements are graph vertices. The vertices are connected iff the correspondent matrix elements are "neighbors" and have the same color. The answer is the number of connected components in the graph.

And the improvement:

Then one has to find the number of "black" and "white" connected components and choose the smallest of both.

This seems to be quite good but the answer is not so simple as it seems at first. Consider this matrix, where there are 13 Black connected components and 4 White ones. :

B w B w B w B w B
w w w w B w w w w
B w B B B B B w B
w w B B B B B w w
B B B B B B B B B  
w w B B B B B w w
B w B B B B B w B
w w w w B w w w w
B w B w B w B w B

The minimal solution is only 2 moves though. First flip (to White) the central big Black component. As a result, the flipped one and the 4 white components are now connected into one component. Flip this to Black and all the board is black.

So, the minimal is only 2 moves, not 4, in this case.

So, after you establish, the connected (black and white components), we have a graph of connections between these components (like in @Biliska's answer). Here's the graph for the above matrix:

        B
        |
     B--w--B
        |
    B   |   B
    |   |   |
B---w---B---w---B
    |   |   |
    B   |   B
        |
     B--w--B
        |
        B

We now need to find the graph's center, or just one of the central points, e.g. a node A where the greatest distance d(A,B) to other nodes B is minimal (and this minimal greatest distance is sometimes called "eccentricity"). It's obvious from the diagram that for the above graph, there is exactly one central point and the "eccentricity" is 2.

When the eccentricity is `n`, there is at least one "maximal" path of length `2n-1` or `2n` (of `2n` or `2n+1` nodes). In our case:

B-w-B-w-B

Since the nodes are sequentially black and white in any path in these graphs, it's not difficult to prove that the minimal changes needed is exactly `n` (2 in this case) and can be achieved by changing always the central area.

Problem

There is a matrix M*N. The matrix elements are either black or white. We call neighboring elements of the same color areas. You can pick any area and flip its color (i.e. change the color of all its elements). Given such a matrix find the minimal number of flips needed to make the whole matrix either black or white. Solution: It looks like a graph problem. The matrix elements are graph vertices. The vertices are connected iff the correspondent matrix elements are "neighbors" and have the same color. The answer is the number of connected components in the graph. Does it make sense? Fixed Solution: Thanks to @ypercube and @Billiska the solution should be fixed as follows: - Find the connected components (as in above) and consider a graph of those components. - Find the graph center, flip it, make a new graph, and repeat until the graph contains only one vertex. We still have to prove though that flipping the graph center makes the number of flips minimal.

Original source