LG#P1451. 求细胞数量

求细胞数量

题目描述

\hspace{15pt}给定一个 n×mn\times m 的数字矩阵。字符 ‘0’\texttt{`0'} 表示空白,字符 ‘1’\texttt{`1'} 到 ‘9’\texttt{`9'} 表示细胞。

\hspace{15pt}上下左右相邻的细胞属于同一块;这种关系可以传递。不同数字的细胞也可以属于同一块,斜对角相邻不算直接相连。请统计矩阵中细胞块的数量。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦100)n,m\left(1\leqq n,m\leqq100\right),代表矩阵的行数与列数。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm 的字符串,仅含数字字符 ‘0’\texttt{`0'} 到 ‘9’\texttt{`9'}。

输出格式

\hspace{15pt}输出一个整数,代表细胞块数量。没有细胞时输出 00。

测试样例

4 10
0234500067
1034560500
2045600671
0000000089
4

样例 1 解释

\hspace{15pt}从左向右观察,包含数字 2,3,4,5,62,3,4,5,6 的左侧区域通过上下左右连接,构成一块;第一列第二、三行的 1,21,2 构成一块;第一行末尾的 6,76,7 构成一块;第二行的 55 与右下角的 6,7,1,8,96,7,1,8,9 相连,构成一块。共 44 块。

2 2
10
02
2