4036: Cow Tipping (cowtip)

【问题描述】

农民约翰偶尔有烦恼，因为一些无聊的青少年会在夜间访问他的农场并使他的奶牛翻倒（脚向上，背在下）。一天早晨，他醒来发现这样的事情再次发生，他的N2头牛原本晚上开始被放牧在一个刚好是N×N的正方形布局的网格中（1≤N≤10），但他现在发现其中一些奶牛现在已经四脚朝天，被翻倒了。

幸运的是，农民约翰用他的一部分拖拉机和叉车改装成一个超级机器，叫“Cow-Untipperator 3000”，它可以一次过立即翻转一大群奶牛，这样就尽可能快地帮他把所有的牛翻回过来。这个机器适用于翻转网格中任一个左上角矩形区域里的奶牛，即这个矩形是包含左上角奶牛的矩形子网格。当他使用时，机器将这个矩形中的每头牛翻转，把牛脚翻回到地上，但不幸的是同时也翻倒本来已经站在地上的奶牛！换句话说，机器所翻转的矩形中每头牛的状态会颠倒。

农民约翰认为，通过充分利用他的机器足够多的次数，以适当的矩形集合，他最终可以把奶牛恢复到的它们正常的状态。请帮助他确定完成任务所需机器的最低数量。

请注意，将机器应用到同一个矩形两次将是毫无意义的，因为这将不会对矩形中的奶牛产生任何影响。

【输入格式】

输入的第一行是整数n

随后有n行，随后每行包含n个0或1的数字（0代表牛脚向下，1代表牛脚向天）。

【输出格式】

请输出农民约翰需要用Cow-Untipperator 3000恢复他所有的牛脚的最小次数。

【输入样例】

3

001

111

111

【输出样例】

2

说明：在这个例子中，如果约翰先将他的机器用于整群奶牛（这是一个有效的左上方的矩形），他将切换其状态如下：

110

000

000

接着就是应用机器到包含两个1的左上方的矩形，然后就完成了。所以总共2次机器。