2148. 大家来找碴

单点时限: 2.0 sec

内存限制: 256 MB

ECNU 喜欢上一个 MM, 但是这个 MM 喜欢玩 ” 大家来找喳 ” 这个游戏,为了赢得 MM 的芳心,ECNU 不得不苦练技术。为了提高技术,所以 ECNU 希望你能帮助他,为了简化问题,ECNU 只想知道给定的一幅图中有多少个物体。

对于一幅图,我们规定物体是由 CS 集合{字母(A~Z,a~z),数字 (1~9)}里的元素组成,不属于 CS 集合的字符不是组成物体的元素。相同的字符,并且它在上下左右四个方向是连通的,那么我们认为它们属于一个物体。我们保证连在一起的相同字符不会超过 1000. 例如:

+---------------------------+

| 1110 | 1110 | 1000 | 1111 |

| 1010 | 1101 | 000z | zzzz |

+---------------------------+

| 一个 | 两个 | 两个 | 两个 |

+---------------------------+

输入格式

第一行一个整数 N(0<N<=20) 表示有组测数据的组数。

每组测试数据的第一行有两个正整数 h,w(0<h,w<1000)。后面 h 行 w 列,由数字或字母组成,描述一幅图的形态

输出格式

对于每组测试数据,输出图中有多少个物体。

样例

Input
3
5 6
011100
000100
000022
222222
000333
4 7
0101000
111100x
0110000
111100x
2 2
@@
&&
Output
3
3
0
Hint:
对于测试数据1:有三个物体,分别为1,2,3。
对于测试数据2:有三个物体,分别为1,x,x。
对于测试数据3:@,&都不属于CS字符集,所以没有物体.

39 人解决,74 人已尝试。

63 份提交通过,共有 163 份提交。

5.0 EMB 奖励。

创建: 13 年,6 月前.

修改: 4 年,3 月前.

最后提交: 2 年,7 月前.

来源: 第一届程序设计竞赛

题目标签