Problem10673--洛谷P10379 - [GESP七级] [202403]俄罗斯方块

10673: 洛谷P10379 - [GESP七级] [202403]俄罗斯方块

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

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

网格图由 $n \times m$ 个带颜色方块构成。小杨同学现在将这个网格图交给了你,请你计算出网格图中俄罗斯方块的种类数。  
如果两个同色方块是四连通(即上下左右四个相邻的位置)的,则称两个同色方块直接连通;若两个同色方块同时与另一个同色方块直接或间接连通,则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过 平移 其中一个俄罗斯方块可以和另一个俄罗斯方块重合;如果两个俄罗斯方块颜色不同,仍然视为同一种俄罗斯方块。

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


Input

第一行包含两个正整数 $n$ 和 $m$,表示网格图的大小。  
对于之后的 $n$ 行,第 $i$ 行包含 $m$ 个正整数 $a_{i1}, a_{i2}, \dots a_{im}$,表示该行 $m$ 个方块的颜色。

Output

输出一行一个整数表示答案。

Constraints

对全部的测试数据,保证 $1 \leq n, m \leq 500$,$1 \leq a_{i,j} \leq n \times m$。

Sample 1 Input

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

Sample 1 Output

7

HINT

洛谷P10379

Source/Category