D. 方格【普及】

内存限制:256 MiB 时间限制:1000 ms 输入文件: grid.in 输出文件: grid.out
题目类型:传统 评测方式:文本比较

题目描述

小 C 和方格是好朋友。

小 C 有一个 n m 列的方格图,每个方格中都有一个数字,其中第 i 行第 j 列的方格中的数字为 a_{i,j}

我们定义,在这个方格图中,两个不同的方格不相邻,当且仅当这两个方格没有公共边

小 C 认为,两个不同的方格互为好朋友,当且仅当这两个方格不相邻这两个方格中的数字相同

小 C 想让你帮忙求出,所有方格的好朋友的数量之和是多少。

输入格式

第一行两个整数 n,m

接下来 n 行,每行 m 个整数,其中第 i 行的第 j 个整数表示 a_{i,j}

输出格式

一个整数,表示所有方格的好朋友的数量之和。

样例

样例输入 #1

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

样例输出 #1

20

【样例解释 #1】

1 行第 1 列的方格共有 3 个好朋友,第 1 行第 2 列的方格共有 2 个好朋友,第 1 行第 3 列的方格共有 1 个好朋友,第 1 行第 4 列的方格共有 0 个好朋友;

2 行第 1 列的方格共有 1 个好朋友,第 2 行第 2 列的方格共有 2 个好朋友,第 2 行第 3 列的方格共有 1 个好朋友,第 2 行第 4 列的方格共有 1 个好朋友;

3 行第 1 列的方格共有 1 个好朋友,第 3 行第 2 列的方格共有 3 个好朋友,第 3 行第 3 列的方格共有 1 个好朋友,第 3 行第 4 列的方格共有 4 个好朋友;

所有方格的好朋友数量之和为 20

数据范围与提示

【数据范围】

对于 100\% 的数据, 1 \le n,m \le 2000 1 \le a_{i,j} \le 9

测试点编号 n,m \le a_{i,j} \le 特殊性质
1\sim3 80 9
4\sim5 2000 1
6\sim7 2000 9
8\sim10 2000 9

特殊性质:保证任意两个相邻的方格中的数不相等。