URAL 1124 - Mosaic

Solution

Model the solution to a graph.
Each box is a vertex, and if box x has a piece with color y, add a directed edge (x, y).
Then, the number of movement is the number of edges plus the number of jumping to another node.

If the graph is undirected, then what we need to do is count the number of odd degree node. (211 homework!)
However, since there are equal number of pieces for all colors, that means for all node x, the number of incoming edges = number of outgoing edges.
That means the number of jumping required = number of connected component - 1

Overall time complexity = O(|V|+|E|) = O(M²)