HX1465. 家族

提交3 通过2
通过率66.7%
时间限制1000ms
内存限制128MiB

题目描述

在一个与世隔绝的岛屿上,同一个家族的人家通过东、南、西、北四个方向相邻的人家连接在一起。不同家族之间有河流、山丘或大海隔开。同一个家族的人不一定有相同的姓氏。

给出岛上的地图,共有 n 行 m 列。空格表示大海,* 表示河流或山丘,小写英文字母表示一户人家的姓氏。请统计地图上共有多少个家族。

只要两户人家上下左右相邻,就属于同一家族,与字母是否相同无关。斜对角相邻不算连通。

输入格式

第一行输入两个整数 n 和 m,分别表示地图的行数和列数。

接下来 n 行,每行包含 m 个字符,表示一行地图。请保留地图中的空格,不要把空格当作分隔符。一行可以全部由空格组成。

输出格式

输出一个整数,表示家族数。

4 8
*zlw**pxh
l*zlwk*hx
w*tyy**yy
******zzl
3

输入样例 #2

1 1
a

输出样例 #2

1

输入样例 #3

1 1
*

输出样例 #3

0

数据范围与约定

1 ≤ n,m ≤ 200。地图字符为小写英文字母、* 或空格。