[GESP202403 七级] 俄罗斯方块

题目描述

小杨同学用不同种类的俄罗斯方块填满了一个大小为 $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},\dots,a_{im}$，表示该行 $m$ 个方块的颜色。

输出格式

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

样例 #1

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 解释

类型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

数据范围

对于占比 $30\%$ 的子任务数据点，保证 $n \leq 20$，$m \leq 20$，$\max a_{ij} \leq 400$，所有的俄罗斯方块大小不超过 $5 \times 5$，即均可以放置于 $5 \times 5$ 的网格图中。

对于占比 $30\%$ 的子任务数据点，保证 $n \leq 500$，$m \leq 500$，$\max a_{ij} \leq 500^2$，所有的俄罗斯方块的形状均为 $1 \times x$ 或 $x \times 1$ 类型，其中 $x$ 为任意正整数。

对于占比 $40\%$ 的子任务数据点，保证 $n \leq 500$，$m \leq 500$，$\max a_{ij} \leq 500^2$。

对于全部数据，保证 $1 \leq n,m \leq 500$，$0 \leq a_{ij} \leq 500^2$。

来源

GESP 2024 年 03 月 C++ 七级 T2