2365. 围成面积
1000ms
256MB
简单
深度优先搜索
DFS
题目描述
在一个大小为 $10 \times 10$ 的二维网格中，包含数字 `0` 和 `1`。其中，数字 `1` 代表边界线，数字 `0` 代表普通区域。
闭合图形的面积定义为：被数字 `1` 所组成的闭合曲线完全围住的 `0` 的个数。
请编写一个程序，计算并输出由数字 `1` 围成的闭合图形的面积。
输入格式
- 输入包含 $10$ 行，每行有 $10$ 个用空格隔开的整数（只能为 `0` 或 `1`），代表二维网格的初始状态。
输出格式
- 输出一个整数，表示闭合图形的面积（即被围住的 `0` 的个数）。
样例 1
输入 (Input)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
输出 (Output)
15
- 网格大小固定为 $10 \times 10$。
- **算法提示**：
这是一道典型的**网格连通性/淹没法（Flood Fill）**问题。
若直接寻找被包围的 `0` 比较困难，我们可以**反向思考**：寻找哪些 `0` 是“没有被包围的”（即能与网格边缘相通的 `0`）。
1. 遍历网格的四条边界（第一行、最后一行、第一列、最后一列）。
2. 如果边界上的某个格子是 `0` 且未被访问，则从该点启动一次 BFS 或 DFS。
3. 搜索过程中，只允许在相邻的 `0` 之间移动。所有被搜索到的 `0` 都是“未被包围的”，将其标记为已访问。
4. 遍历完全图后，统计网格中所有值为 `0` 且未被访问标记过的格子数量，此数量即为被包围的面积。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功