Official Analysis (C++)

Explanation

As with many problems, the trick is to start in reverse.

We look for all 2 by 2 regions (henceforth referred to as just "regions") that could have been painted last (possible if all four squares are the same color) and expand outward from them.

We can do this because after "covered" some initial regions, we now can "tuck in" adjacent regions that can't be painted so easily into the parts that were already covered.

For example, consider this area where we cover the center region of $0$s first:

After we did that, we can now cover the $1$s by first painting them and then painting over the center region with $0$s.

That region of $0$s only affects our opinion of the surrounding 4 by 4 area; no other part of the canvas is affected.

There's only $8$ other regions (not counting the original one that was just painted over) that could have been made valid by covering one, so there aren't too many edges to consider.

Implementation

Regions are represeted by the index of their upper left corner.

Time Complexity: $\mathcal{O}(nm)$

Copy
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;