#HX1218AA. 【GESP强化 六级】细胞数字

提交1 通过1
通过率100%
时间限制3000ms
内存限制256MiB
    ID: 10519 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 普及 上传者: 标签>GESPGESP强化C++c++编程题昊轩OJ深度优先搜索1星

题目描述

一个 mmnn 列的数字矩阵由数字 09 组成。其中,数字 0 表示背景,数字 19 表示细胞数字。

如果两个细胞数字所在的格子上下或左右相邻,则它们属于同一个细胞。这个关系具有传递性:只要两个非零格能够通过若干次上下左右移动相互到达,它们就属于同一个细胞。同一个细胞中的数字不要求相同。

请计算矩阵中共有多少个细胞。

输入格式

第一行包含两个整数 m,nm,n,分别表示矩阵的行数和列数。

接下来 mm 行,每行包含一个长度为 nn 的数字串。每个字符都是 09 中的一个数字,字符之间没有空格。

输出格式

输出矩阵中的细胞数量。

4 10
0234500067
1034560500
2045600671
0000000089
4
1 1
9
1
2 8
03200611
36026080
3

样例说明

所有非零格按上下左右连通关系划分为 44 个细胞。

数据范围

1m,n601\le m,n\le60