背景

GESP七级真题(202403)

描述

小杨同学用不同种类的俄罗斯方块填满了一个大小为 $n \times m$ 的网格图。

网格图由 $n \times m$ 个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。

如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。

例如，在如下情况中，方块 1 和方块 2 是同一种俄罗斯方块，而方块 1 和方块 3 不是同一种俄罗斯方块。

方块1：  方块2：  方块3： 
1 1 1    2 2 2       1 
1 1        2 2     1 1 
                   1 1

格式

输入

第一行包含两个正整数 $n, m$ ，表示网格图的大小。

对于之后 $n$ 行，第 $i$ 行包含 $m$ 个正整数 $a_{i1}, a_{i2}, ... , a_{im}$ ，表示该行 $m$ 个方块的颜色。

输出

输出一个非负整数，表示俄罗斯方块的种类数。

样例

5 6 
1 2 3 4 4 5 
1 2 3 3 4 5 
1 2 2 3 4 5 
1 6 6 7 7 8 
6 6 7 7 8 8

7

样例解释

种类型的俄罗斯方块如下：

类型1： 类型2： 类型3： 类型4： 类型5： 类型6：        类型7： 
1       2       3      4 4      5     6 6   7 7       8 
1       2       3 3      4      5   6 6   7 7       8 8 
1       2 2       3      4      5 
1

数据规模

对于所有测试点，保证 $1 \le n, m \le 500, 0 \le a_{ij} \le 500^2$。

限制

时间限制：1.0 s

空间限制：128.0 MB