H. 【普及】网格中连通块个数

A B C D E F G H I J K

传统题

100ms

32MiB

题目背景

注意：请分别用 bfs 和 并查集 通过本题目！！

1、在上一题中，我们学会了如何用 bfs 和 并查集 计算图中的连通块个数
2、在本题中，我们要求的是网格中的连通块个数

题目描述

给你一个只包含 0 和 1 的大小为 $n \times m$ 的迷宫

1、其中 1 表示可通行，0 表示无法通行
2、在任何一个为 1 的位置，都可以走到上，下，左，右中，也为 1 的位置

请问该迷宫中，有多少个连通块

输入格式

第一行包含 $2$ 个整数 $n, m$

接下来 $n$ 行，每行包含 $1$ 个长为 $m$ ，且只包含 0 和 1 的字符串

输出格式

输出连通块的个数

提示

【样例 1 解释】

图中的 $2$ 个连通块为 $\{1, 2\}, \{3, 4, 5\}$

【数据范围】

对于所有测试数据，均有：

$1 \le n \times m \le 10^5$

请思考后再点击查看提示

来源

【2026-01-10】学校要封校，不能上课，我们寒假再见（请大家点开作业）

状态: 正在进行…
题目: 11
开始时间: 2026-1-7 8:00
截止时间: 2027-8-22 23:59
可延期: 24 小时