← 返回题目列表

Codeforces · 316/C1

C1. 整理

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

聪明海狸很注重自己的外表,并且特别注重鞋子,因此他拥有大量森林中最著名品牌的鞋子。他小心翼翼地处理自己的鞋子,让每一双鞋子都并排放置。但到了周末,由于他非常活跃的生活方式,更衣室变得一团糟。

ABBYY 的 Smart Beaver 不仅是该地区最聪明的海狸,而且也是最注重国内的。例如,每周一,聪明海狸都会清理家里的所有东西。

现在是星期一早上。聪明海狸不想花一整天的时间打扫卫生,而且还有很多事情要做,而且今天是健身房,所以他想尽快打扫干净。现在地板已经洗干净,灰尘也擦掉了——是时候清理更衣室了。但聪明海狸一进入更衣室,当天的所有计划就突然被破坏了:那里一片混乱,似乎根本无法处理,哪怕是一周。给我们的英雄一些希望:告诉他最少需要多少双鞋才能改变位置以使更衣室整洁。

更衣室是长方形的,被分成n×m个相等的方格,每个方格恰好包含一只鞋子。每双鞋都有一个唯一的编号,该编号是 1 到 $${ \frac { n \cdot m } { 2 } }$$ 之间的整数,更正式地说,坐标为 (i, j) 的正方形包含位于其上的一双鞋的整数。聪明的海狸相信,只有当每双运动鞋放在一起时,更衣室才是整洁的。我们假设正方形 (i1, j1) 和 (i2, j2) 中的一双运动鞋放在一起,如果 |i1 - i2| + |j1 - j2| = 1。

输入

第一行包含两个空格分隔的整数 n 和 m。它们与更衣室的大小相对应。接下来的 n 行每行包含 m 个空格分隔的整数。这些数字描述了更衣室。每个数字对应一个窃笑。

保证:

- n·m 是偶数。
- 与更衣室中鞋子的数量相对应的所有数字都将位于 1 和 $${ \frac { n \cdot m } { 2 } }$$ 之间。
- 从 1 到 $${ \frac { n \cdot m } { 2 } }$$ 的每个数字将恰好出现两次。

得分 30 分的输入限制为(子问题 C1):

- 2 ≤ n, m ≤ 8。

获得 100 分的输入限制为(子问题 C1+C2):

- 2 ≤ n, m ≤ 80。

输出

精确打印一个整数——需要改变位置的运动鞋的最少数量。

示例

输入 #1

2 3
1 1 2
2 3 3

输出 #1

2

输入 #2

3 4
1 3 2 6
2 1 5 6
4 4 5 3

输出 #2

4

注意

第二个样本。