Cow Tipping

题目描述

Farmer John 偶尔会被夜里来农场捣乱的无聊青少年所困扰，他们会把他的奶牛掀翻。某天早晨，他醒来发现这事又发生了——他的 $N^2$ 头奶牛在夜晚开始时以完美的 $N \times N$ 方格排列（$1 \leq N \leq 10$），但他发现其中一些现在被掀翻了。 幸运的是，Farmer John 用拖拉机和叉车的零件打造了一台辉煌的机器：Cow-Untipperator 3000，它可以一次翻起一大群奶牛，帮助他尽快把所有奶牛都扶正。他可以把机器作用于奶牛网格中的任意一个“左上矩形”——一个包含左上角那头奶牛的矩形子网格。每次这样做，机器会翻转该矩形中的每一头奶牛：把被掀翻的奶牛扶正，但不幸的是也会把原本站着的奶牛掀翻！换句话说，这台机器会“切换”矩形内每头奶牛的状态。 Farmer John 认为，只要对合适的一组矩形应用足够多次机器，他最终就能让所有奶牛恢复为正确的未掀翻状态。请帮助他确定为此所需的最少机器使用次数。 注意，对同一个矩形连续使用两次机器是没有意义的，因为这不会对该矩形中的奶牛产生任何净影响。因此，你只需要考虑对每个左上矩形至多使用一次机器。

输入格式

第一行是整数 $N$。 接下来的 $N$ 行每行包含一个长度为 $N$ 的字符串，每个字符要么是 0（表示未掀翻的奶牛），要么是 1（表示被掀翻的奶牛）。

输出格式

请输出 Farmer John 需要使用 Cow-Untipperator 3000 的最少次数，使所有奶牛都恢复站立。

3
001
111
111

2

提示

在该示例中，如果 FJ 将机器作用于整个牛群（这也是一个合法的左上矩形），他会将它们的状态切换为如下所示： 110 000 000 剩下的只需要再对包含两个 1 的左上矩形使用一次机器即可完成。总共只需要 2 次使用。 题目贡献：Nathan Pinsker

标签: USACO|2017|Bronze

来源

USACO|2017|Bronze