#O1039. 连通块计数

连通块计数

题目描述

给定 n×mn \times m 的 01 网格,求由 1 组成的四连通块个数(上下左右相邻视为连通)。

题目类型

深度优先搜索、连通块

输入格式

第一行两个整数 n,mn, m。

接下来 nn 行,每行一个长度为 mm 的 01 串。

输出格式

一行一个整数,表示连通块个数。

样例 #1

样例输入 #1

3 3
110
010
001

样例输出 #1

2

数据规模与约定

数据范围 说明
1≤n,m≤10001 \le n, m \le 1000 网格规模
  • 递归过深会爆栈,可改用 BFS 或手写栈。