CODEWITHSUNDEEP
algorithmlanguage-agnosticgraphmatrix
Michael
Michael

Reputation: 42050

Riddle: How to change matrix color?

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:

We still have to prove though that flipping the graph center makes the number of flips minimal.

Upvotes: 3

Views: 1198

Answers (3)

Apiwat Chantawibul
Apiwat Chantawibul

Reputation: 1463

First, you are off that trying to model the problem as a connection graph of cells when in fact you should model the problem as a connection graph of areas

For exapmle

b w b w b
w b b w b
w w b b w

transformed into area notation as:

1 2 3 4 5
6 3 3 4 5
6 6 3 3 7

which is better represented as:

1 - 2   4 - 5
|   | /     |
6 - 3 - - - 7

Now the next thing to do is to repeatedly perform flip operation to merge the areas. I'm not sure if greedily flip the area with most connections will be correct or not.

For example I'll flip area 3 first because it has 4 connections. Then I get:

1       5
  \   /
   (3)

Then flip area 3 again because it has 2 connections:

   (3)

done

So you can see flip operation has the effect of merging all adjacent nodes into the one being flipped.

EDIT: in fact, greedily flip area with most connections isn't optimal. Take the 1-dimension example I commented earlier.

input:

             middle
                v
b w b w b w b w b w b w b w b w b
<---4 times--->   <---4 times--->

You can see that the most connections any area has is of degree 2. But the most efficient algorithm will only choose to flip the middle area.

Upvotes: 3

ypercubeᵀᴹ
ypercubeᵀᴹ

Reputation: 115530

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.

Upvotes: 5

amit
amit

Reputation: 178451

This problem can be solved as a shortest path problem.

Model your problem as a state graph G=(V,E) where V = possible states (matrix states) and E = { (u,v) | can move from state u to state v with single "flip" }

Now, once you have the graph - all you have to do is use some shortest path algorithm.

Since the graph is unweighted - you can use BFS as your shortest path algorithm. If you can find some admissible heuristic function - you might also be able to use A* algorithm - which is expected to be faster with a descent heuristic.

Upvotes: 3

Related Questions