Flood Fill#13028

Flood Fill (Editorial)

Author:

Lucian Bicsi

Let's look at each initial connected component in picture . For each component, we can either leave the colour the same, or change it. Let's choose for each component what we'll do. Which situations are impossible? Well, it's not hard to see that two neighbouring components cannot both change colour, because once one of them changes colour, they will have the same colour, and we can't change that in the future.

Let's build a graph: the vertices are connected components and they are connected if they have a common border. Based on previous observation, the set of components in which you want to change the colour should form an independent set in this graph. And it's clearly possible for any independent set: just use the operation on the components you want, since they are not neighbours they don't affect each other (so the sample explanation is a red herring actually, you never have to apply the operation on the same component more than once).

For each component we can calculate the score if we change the colour in it and if we don't, now we want to find weighted maximum independent set in the graph we constructed. Our graph is bipartite since two neighbouring components have different colours. It's a standard problem, which is reduced to max flow.