[USACO 2017 Jan B]Cow Tipping

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 it has happened again -- his

cows began the night grazing in a perfect N×N square grid arrangement (1≤N≤10), but he finds that 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 over large groups of cows all at once, helping him put 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 over every cow in this rectangle, placing tipped cows back on their feet, but unfortunately also tipping over cows that were already on their feet! In other words, the machine "toggles" the state of each cow in the rectangle.

Farmer John figures that by applying his machine sufficiently many times to the appropriate collection of rectangles, he can eventually restore all the cows to their rightful, un-tipped states. Please help him determine the minimum number of applications of his machine needed to do this.

Note that applying the machine to the same rectangle twice would be pointless, since this would have no net impact on the cows in the rectangle. Therefore, you should only consider applying the machine to each upper-left rectangle possibly only once.

#!/usr/bin/env python3 # # Cow Tipping # import sys, os, math def read_ints(): return list(map(int, input().split())) n = int(input()) a = [input() for _ in range(n)] c = [[0] * n for _ in range(n)] c[n - 1][n - 1] = int(a[n - 1][n - 1]) for i in range(n - 1, -1, -1): for j in range(n - 1, -1, -1): if i == n - 1 and j == n - 1: continue elif i == n - 1: c[i][j] = c[i][j + 1] + (1 if int(a[i][j]) != c[i][j + 1] % 2 else 0) elif j == n - 1: c[i][j] = c[i + 1][j] + (1 if int(a[i][j]) != c[i + 1][j] % 2 else 0) else: c[i][j] = c[i + 1][j] + c[i][j + 1] - c[i + 1][j + 1] if int(a[i][j]) != c[i][j] % 2: c[i][j] += 1 print(c[0][0])

#include<cstdio> using namespace std; int map[110][110]; int main() { int n,i,j,u,v,ans=0; char c; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf(" %c",&c); map[i][j]=c-'0'; } for(i=n;i>0;i--) for(j=n;j>0;j--) if(map[i][j]) { for(u=1;u<=i;u++) for(v=1;v<=j;v++) map[u][v]^=1; ans++; } printf("%d\n",ans); return 0; }

详情