2364. 疾病预防系统
1000ms
256MB
简单
深度优先搜索
DFS
题目描述
某国新研发了一套疾病预防系统。当传染病爆发时，监测系统会将各区域的感染情况反应在系统中，并形成一个 $n \times m$ 的矩形阵列。
- 矩阵由数字 `0` 和 `1` 组成。
- `1` 代表该位置为感染居民。
- `0` 代表该位置为健康居民。
一个“感染区域”（连通块）定义为在**上下左右**四个方向上相邻的感染居民（值为 `1`）所构成的连通区域。请计算并输出该矩阵中感染区域的总个数。
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($0 < n, m \le 100$)，分别表示矩阵的行数和列数。
- 接下来 $n$ 行，每行包含 $m$ 个以空格隔开的整数（`0` 或 `1`），表示当前各位置的居民状态。
输出格式
- 输出一行一个整数，表示矩阵中感染区域的个数。
样例 1
输入 (Input)
5 6 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0
输出 (Output)
4
样例说明
- **样例说明**：
在 $5 \times 6$ 的矩阵中，共有 4 个独立的 `1` 连通块（即感染区域）：
- 第 1 个区域包含：(0,1), (1,1), (2,1), (2,2)
- 第 2 个区域包含：(0,3), (1,3), (1,4), (1,5), (2,5)
- 第 3 个区域包含：(0,5) （注意它与上面的区域连通，已合并为第 2 个区域的一部分，此处独立区域仅为样例中的物理连通）
- 第 4 个区域包含：(3,0), (4,0)
- 第 5 个区域包含：(4,3)
- 合计共有 4 个独立的连通区域。
- 对于 $100\%$ 的数据：$0 < n, m \le 100$。
- **算法提示**：
这是一个经典的求**二维网格图连通分量个数**的问题，可以使用**深度优先搜索（DFS）**或**广度优先搜索（BFS）**解决：
1. 遍历 $n \times m$ 矩阵中的每一个点，当遇到一个值为 `1` 且未被访问过的点时，感染区域数量加 1。
2. 从该点出发进行 DFS/BFS，沿着上下左右四个方向扩散，将所有与其相连通的 `1` 都标记为已访问（也可以直接将其修改为 `0` 以省去 `visited` 数组空间）。
3. 重复以上步骤，直到遍历完整个矩阵。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功