Cow Tipping#10546
Farmer John occasionally has trouble with bored teenagers who visit his farm at night and tip over his cows. One morning, he wakes up to find that it has happened again: his n^2 cows began the night grazing in a perfect n \times n square grid, but some of them are now tipped over.
Fortunately, Farmer John has used parts from his tractor and forklift to build a glorious machine, the Cow-Untipperator 3000, that can flip large groups of cows all at once, helping him get all his cows back on their feet as quickly as possible. He can apply the machine to any "upper-left rectangle" in his grid of cows—a rectangular sub-grid that contains the upper-left cow. When he does so, the machine flips every cow in this rectangle, putting tipped-over cows back on their feet but unfortunately also tipping over cows that were already standing! In other words, the machine "toggles" the state of every cow in the rectangle.
Farmer John figures that by applying his machine sufficiently many times to an appropriate collection of rectangles, he can eventually restore all the cows to their upright positions. Please help him determine the minimum number of machine applications needed to do this.
Note that applying the machine to the same rectangle twice would be pointless, since this would have no net effect on the cows in the rectangle. Therefore, each upper-left rectangle should be considered for use at most once.
The first line contains the integer n~(1 \le n \le 10). Each of the next lines contains a string of characters, each either (representing an upright cow) or (representing a tipped-over cow).
Print the minimum number of times Farmer John needs to apply the Cow-Untipperator 3000 to restore all his cows to their upright positions.
In this example, if FJ applies his machine to the entire grid of cows (which is a valid upper-left rectangle), it toggles their states to the following:
110
000
000All that remains is to apply the machine to the upper-left rectangle containing the two 1s, after which he is finished. In total, this requires just applications.
Example 1