2343. 统计林地
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
最近国家对大兴安岭地区进行林地统计。土地由数字 0 到 9 组成的矩阵表示：
- 数字 `1` 到 `9` 代表各种品种的林地区域。
- 数字 `0` 表示非林地区域。
一个“林地区域”（连通块）定义为**上下左右**相邻的非 0 数字的连通区域。请计算并输出该矩阵中林地区域的总个数。
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($0 < n, m \le 100$)，表示矩阵的行数和列数。
- 接下来 $n$ 行，每行包含一个长度为 $m$ 的由字符 `0`~`9` 组成的字符串（各字符间无空格），代表矩阵。
输出格式
- 输出一行一个整数，表示林地区域的个数。
样例 1
输入 (Input)
4 10 0234500067 1034560500 2045600671 0000000089
输出 (Output)
4
- 对于所有数据：$0 < n, m \le 100$。
- **输入陷阱提示**：
注意输入数据中每行的字符**没有空格分隔**（例如：`0234500067`）。因此在 C++ 中不能直接使用 cin >> int 来读取每个格子，否则会将整行误读为一个巨大的整数。建议使用 `std::string` 或 `char` 数组按行读取，再对每个字符进行处理。
- **算法提示**：
这是一个经典的求**二维网格图连通块数量**的问题，可以使用**深度优先搜索（DFS）**或**广度优先搜索（BFS）**解决：
1. 遍历 $n \times m$ 矩阵中的每一个点，当遇到一个非 `0` 且未被访问过的点时，连通块数量加 1。
2. 从该点出发进行 DFS/BFS，沿着上下左右四个方向扩散，将所有与其相连通的非 `0` 点都标记为已访问。
3. 重复以上步骤，直到遍历完整个矩阵。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功