试题名称:俄罗斯⽅块
3.2.1 题面描述
⼩杨同学⽤不同种类的俄罗斯⽅块填满了⼀个⼤⼩为nxm的⽹格图。
⽹格图由n×m个带颜⾊⽅块构成 。⼩杨同学现在将这个⽹格图交给了你 ,请你计算出⽹格图中俄罗斯⽅块的种类数。
如果两个同⾊⽅块是四连通(即上下左右四个相邻的位置) 的 ,则称两个同⾊⽅块直接连通 ;若两个同⾊⽅块同时 与另⼀个同⾊⽅块直接或间接连通 ,则称两个同⾊⽅块间接连通 。⼀个俄罗斯⽅块由⼀个⽅块和所有与其直接或间 接连通的同⾊⽅块组成 。定义两个俄罗斯⽅块的种类相同当且仅当通过平移其中⼀个俄罗斯⽅块可以和另⼀个俄罗 斯⽅块重合 ;如果两个俄罗斯⽅块颜⾊不同 ,仍然视为同⼀种俄罗斯⽅块。
例如 ,在如下情况中 ,⽅块1和⽅块2是同⼀种俄罗斯⽅块 ,⽽⽅块1和⽅块3不是同⼀种俄罗斯⽅块。
3.2.2 输入格式
第⼀⾏包含两个正整数n ,m ,表⽰⽹格图的⼤⼩ 。
对于之后n⾏ ,第i⾏包含m个正整数ai1,ai2 …, ,aim,表示该行m个方块的颜色。
3.2.3 输出格式
输出⼀个⾮负整数 ,表⽰俄罗斯⽅块的种类数。
3.2.4 样例 1
3.2.5 样例解释
7 种类型的俄罗斯⽅块如下:
3.2.6 数据范围
对于全部数据 ,保证有1≤n, m≤500 ,0≤aij≤5002 。