← 返回题单

题单练习 2024年3月GESP编程题

← 上一题下一题 →

A5283 | $[GESP202403 七级] 俄罗斯方块$

来源2024

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

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

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示网格图的大小。 对于之后的 $n$ 行，第 $i$ 行包含 $m$ 个正整数 $a_{i1}, a_{i2}, \dots a_{im}$，表示该行 $m$ 个方块的颜色。 子任务分数$n,m \leq$特殊约定$1$$30$$20$所有俄罗斯方块大小不超过 $5 \times 5$$2$$30$$500$所有俄罗斯方块大小均为 $1 \times x$ 或 $x \times 1$ 类型，其中 $x$ 是任意正整数$3$$40$$500$无 对全部的测试数据，保证 $1 \leq n, m \leq 500$，$1 \leq a_{i,j} \leq n \times 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

输出 #1

C++ 编辑器

输入

输出