The Components Game

This game gives you a grid of 0 and 1 and asks you to replace any column with all 0 such that the number of distinct regions of 0 and 1 are maximized.

First note we can count regions by flood-filling them with some other number (say, a unique index for that region) until no 1's or 0's are left.

We only have 1000 columns, so we can easily brute force try every column. We cannot, however, calculate the region count each time, since that's 1000x1000 to do the (too slow to do it for every one!). So we need at worst an o(1000) evaluation time for each column. We can do this though, quite easily.

1. all black regions in that row and to the left and right are joined. We can identify all the unique regions it joins and subtract them from our total
2. if all squares to the left and right are white, we add a black region
3. any white region which spans the column is split. (fortunately, if it spans this column, we will find some square on the left and right that have the same region index
4. any white region which is entirely contained in this column is eliminated

Compute this count for every column, and return the best (don't forget the tiebreaker!)