CF1648A Weird Sum

Egor 有一个大小为 $n \times m$ 的表格，行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。每个单元格都有一个颜色，可以用 $1$ 到 $10^5$ 之间的整数表示。 我们用 $(r, c)$ 表示第 $r$ 行第 $c$ 列的单元格。我们定义两个单元格 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的曼哈顿距离为它们之间最短路径的长度，其中路径上的每一对相邻单元格必须有公共边。路径可以经过任意颜色的单元格。例如，在 $3 \times 4$ 的表格中，$(1, 2)$ 和 $(3, 3)$ 之间的曼哈顿距离为 $3$，其中一条最短路径为：$(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$。 Egor 决定计算所有颜色相同的单元格对之间的曼哈顿距离之和。请你帮他计算这个和。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m$，$n \cdot m \leq 100\,000$），表示表格的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$（$1 \leq c_{ij} \leq 100\,000$），表示第 $i$ 行每个单元格的颜色。

输出一个整数，表示所有颜色相同的单元格对之间的曼哈顿距离之和。

在第一个样例中，有三对颜色相同的单元格：$(1, 1)$ 和 $(2, 3)$，$(1, 2)$ 和 $(2, 2)$，$(1, 3)$ 和 $(2, 1)$。它们之间的曼哈顿距离分别为 $3$、$1$ 和 $3$，总和为 $7$。 由 ChatGPT 4.1 翻译