← 返回题目列表

Codeforces · 126/C

C. 电子阅读器显示屏

中文机器翻译题面 查看原题

经过多年的努力,科学家们发明了一种全新的电子阅读器显示器。新的显示器具有更大的分辨率、消耗更少的能量并且其生产更便宜。此外,人们还可以弯曲它。唯一的不便是非常不寻常的管理。正是出于这个原因,开发人员决定将电子阅读器的软件留给程序员。

显示由 n × n 的像素正方形表示,每个像素可以是黑色或白色。显示行从左到右用 1 到 n 的整数编号,列从左到右用 1 到 n 的整数编号。显示器可以执行“x,y”等命令。当传统显示器执行此类命令时,它只是反转 (x, y) 的颜色,其中 x 是行号,y 是列号。但在我们的新显示器中,至少属于 (x, x) - (x, y) 和 (y, y) - (x, y) 段(包括两个段的两端)之一的每个像素都会反转颜色。

例如,如果最初尺寸为 5 × 5 的显示器是绝对白色的,则命令序列 (1, 4)、(3, 5)、(5, 1)、(3, 3) 会导致以下变化:

您是一名电子阅读器软件程序员,您应该计算显示图片所需的最少命令数。您可以将所有显示像素视为最初为白色。

输入

第一行包含数字 n (1 ≤ n ≤ 2000)。

接下来n行每行包含n个字符:需要显示的图片的描述。 “0”代表白色,“1”代表黑色。

输出

打印一个整数 z — 显示图片所需的最少命令数。

示例

输入 #1

5
01110
10010
10001
10011
11110

输出 #1

4