CF316C1 Tidying Up

聪明的海狸非常注重自己的外表，尤其是鞋子，因此他拥有森林中最著名品牌的大量鞋子。他总是小心地整理鞋子，使每一双鞋都并排放好。但由于他非常活跃，到了一周末，他的更衣室总是一团糟。 来自 ABBYY 的聪明海狸不仅是这片区域最聪明的海狸，也是最顾家的。例如，每到周一，聪明海狸都会把家里打扫干净。 现在是周一早晨。聪明海狸不想花整天时间打扫卫生，毕竟还有很多事情要做，而且今天还要去健身房，所以他想尽快收拾完。现在地板已经擦干净，灰尘也已经清理干净——是时候整理更衣室了。但当聪明海狸走进更衣室时，他一天的计划突然被打乱了：里面一片混乱，看起来即使一周也难以整理好。请给我们的主人公一些希望：告诉他，最少需要移动多少只鞋子，才能让更衣室变得整洁。 更衣室是一个 $n \times m$ 的矩形，被划分为 $n \times m$ 个相同的格子，每个格子里正好有一只鞋。每一双鞋都有一个唯一的编号，编号是从 $1$ 到 $k$ 的整数（其中 $k = \frac{n \times m}{2}$）。更正式地说，坐标为 $(i, j)$ 的格子里放着一只鞋，其编号为该双鞋的编号。聪明海狸认为，只有当每一双运动鞋都并排放置时，更衣室才算整洁。我们认为，如果编号为同一双鞋的两只鞋分别在格子 $(i_1, j_1)$ 和 $(i_2, j_2)$，且 $|i_1 - i_2| + |j_1 - j_2| = 1$，那么这双鞋是并排放置的。

第一行包含两个用空格分隔的整数 $n$ 和 $m$，表示更衣室的大小。接下来的 $n$ 行，每行包含 $m$ 个用空格分隔的整数，描述了更衣室的情况。每个数字表示该格子里鞋子的编号。 保证： - $n \cdot m$ 是偶数。 - 所有鞋子的编号都在 $1$ 到 $k$ 之间（$k = \frac{n \times m}{2}$）。 - 每个编号从 $1$ 到 $k$ 恰好出现两次。 对于 30 分的输入数据（子任务 C1）： - $2 \leq n, m \leq 8$。 对于 100 分的输入数据（子任务 C1+C2）： - $2 \leq n, m \leq 80$。

输出一个整数，表示最少需要移动多少只鞋子，才能让更衣室变得整洁。

 这是第二个样例的示意图。 由 ChatGPT 4.1 翻译