#CW77. 差值求和(sum)
差值求和(sum)
题目描述
给定一个大小为 的表格,行编号为 ,列编号为 。第 行第 列的格子记为 ,并带有颜色 。
两个格子之间只能沿公共边移动。格子 与 的曼哈顿距离定义为从一个格子走到另一个格子所需的最少步数,即 。
请计算所有颜色相同且位置不同的格子对的曼哈顿距离之和,每一对只计算一次。
输入格式
从 sum.in 文件中读入。
第一行包含两个整数 ,满足 且 。接下来 行,每行包含 个整数 ,满足 。
输出格式
向 sum.out 文件中输出。
输出一个整数,表示所求的距离总和。答案可能超过 32 位有符号整数范围。
样例 1 输入
2 3
1 2 3
3 2 1
样例 1 输出
7
样例 2 输入
3 4
1 1 2 2
2 1 1 2
2 2 1 1
样例 2 输出
76
样例 3 输入
4 4
1 1 2 3
2 1 1 2
3 1 2 1
1 1 2 1
样例 3 输出
129
数据范围
所有输入数据均为整数。设 为表格中出现的不同颜色数。
本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 23 | ||
| 2 | 17 | ||
| 3 | 15 | ||
| 4 | 20 | ||
| 5 | 25 | 无额外限制 |