第21470题 程序题
统计网格图中俄罗斯方块的种类数

题面描述

小杨同学用不同种类的俄罗斯方块填满了一个大小为n×m的网格图。网格图由n×m个带颜色方块构成,请你计算出网格图中俄罗斯方块的种类数。

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

输入格式

第一行包含两个正整数n,m,表示网格图的大小。 接下来n行,第i行包含m个正整数a<sub>ij</sub>,表示该行第j个方块的颜色。

输出格式

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

样例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

样例解释

样例输入中共包含7种不同形状的俄罗斯方块,分别对应不同的连通块形状。

数据范围

子任务编号 数据点占比 n m max a<sub>ij</sub> 特殊条件
1 30% ≤20 ≤20 ≤400 所有俄罗斯方块大小不超过5×5,即可放置于5×5的网格中
2 30% ≤500 ≤500 ≤500² 所有俄罗斯方块的形状均为1×x或x×1的长条
3 40% ≤500 ≤500 ≤500² 无特殊条件

对于全部数据,保证1≤n, m≤500,0≤a<sub>ij</sub>≤500²。

编辑模式
程序运行统计
暂无判题统计