Quizz..
You have found an ancient carpet in your attic. It was originally black, but during it’s long life it obtained some white stains. Since it is so old we can’t remember maybe it was a white carpet, and the stains are black! You can not tell if it was white or black! Luckily you have found a bottle of Universal Spot Remover. A single drop of this magic liquid can change the color of any white spot to black, no matter how big the spot is. Amazingly, the same drop, if applied to a black spot, would change the color to white! You would like to remove all spots from the carpet. Since you do not know if it was initially black or white, you would be happy to have a carpet that is either completely black OR completely white. Just don’t waste the remover!
Your Task:
Write a program that finds the minimum number of drops needed to remove all stains from the carpet. Assume that the carpet is a MxN rectangle divided into M*N regular checks, some of which are black, some white. The stain is a group of checks of the same color connected side-by-side. For example, if the carpet were 8×8 (with alternating colors, like a chessboard), there would be exactly 32 white and 32 black stains. Note that when you remove a stain, it will merge with other neighboring stains.
Via RSDN
Upd: Answer can easily be found using Graph theory (look for something about finding the longest route in a graph or similar). Or, I just used a hint (chessboard) from the task, considering which it is easy to see that 3 drops would be enough for a carpet of 8×8 stains. The rest is trivial.