面积即被 * 围住的 0 格个数：从最外圈的 0 格做一次多源 BFS 洪水填充，把能走到边界的 0 全标成外部，剩下未标记的 0 就是内部面积，O(nm)。
OJ: roj
题目 ID: 1359
难度:普及-
标签:搜索BFS洪水填充网格python
创建: 2026-09-30 07:02
更新: 2026-10-07 13:50
题目描述
在一个 * 围成若干闭合曲线。统计 * 围成的闭合曲线中水平线和垂直线交点的数目，即为图形的面积。例如样例中 * 围住了 15 个点，面积为 15。
输入为 10 行，每行 10 个用空格分隔的 0/1 整数，1 表示 *；输出面积（一个整数）。样例输入（前 5 行为 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，后 5 行为 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），样例输出为：
text
15思路
“被 * 围住"等价于"该 0 格与网格边界不连通”。反过来做：从最外圈的所有 0 格出发做一次多源 BFS 洪水填充，只穿过 0 格，能走到的都是外部格；剩下未被染色的 0 格就是被围住的内部点，其个数即面积。曲线是否有缺口无需单独判断——有缺口时洪水会漏进去，内部点自动被染成外部。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:02
# update_at: 2026-09-30 07:02
import sys
from collections import deque
from collections.abc import Iterator
SIZE = 10 # 题面固定 10×10
def neighbors(cell: tuple[int, int]) -> Iterator[tuple[int, int]]:
"""产出上下左右四个相邻格（可能越界，由调用点判边界）。"""
r, c = cell
yield r - 1, c
yield r + 1, c
yield r, c - 1
yield r, c + 1
def solve() -> None:
# 按行优先读扁平 token：真实数据里有测例只给了 9 行，缺的行自然补 0（仍是 0，不影响答案）。
grid = [[0] * SIZE for _ in range(SIZE)]
for i, value in enumerate(map(int, sys.stdin.buffer.read().split())):
grid[i // SIZE][i % SIZE] = value # i 超过 100 的部分被丢弃
outside = [[False] * SIZE for _ in range(SIZE)]
queue: deque[tuple[int, int]] = deque()
# 边界上的 0 都是外部：从它们洪水填充，能走到的 0 全部属于图形外。
for r, c in [
(r, c)
for r in range(SIZE)
for c in range(SIZE)
if grid[r][c] == 0 and (r in (0, SIZE - 1) or c in (0, SIZE - 1))
]:
if not outside[r][c]:
outside[r][c] = True
queue.append((r, c))
while queue:
r, c = queue.popleft()
for nr, nc in neighbors((r, c)):
in_board = 0 <= nr < SIZE and 0 <= nc < SIZE
if in_board and grid[nr][nc] == 0 and not outside[nr][nc]:
outside[nr][nc] = True
queue.append((nr, nc))
# 剩下没被外部染色到的 0，就是被 * 围住的内部点，个数即面积。
print(sum(grid[r][c] == 0 and not outside[r][c] for r in range(SIZE) for c in range(SIZE)))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 12:00
* update_at: 2026-10-05 12:01
*/
#include <cstdio>
typedef long long ll;
const int N = 10; // 题面固定 10×10 的网格
int grid[N][N]; // grid[r][c]：1 表示 *（墙），0 表示待判定的点
bool outside[N][N]; // outside[r][c]：该 0 格是否已被判定为外部
// 多源 BFS 洪水填充：从边界上的所有 0 格出发，把能走到的 0 格全部染成外部。
// 只穿过 0 格，遇到 1（墙）就停；曲线有缺口时洪水会漏进去，缺口自动被识别。
void bfs_fill() {
int qx[N * N], qy[N * N]; // 队列存格子坐标，队列含义：待扩散的外部格
int head = 0, tail = 0;
// 种子：最外圈上的 0 格一定属于外部，全部入队
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (grid[r][c] == 0 && (r == 0 || r == N - 1 || c == 0 || c == N - 1)) {
outside[r][c] = true;
qx[tail] = r;
qy[tail] = c;
tail++;
}
while (head < tail) {
int r = qx[head], c = qy[head];
head++;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向相邻
for (int k = 0; k < 4; k++) {
int nr = r + dir[k][0], nc = c + dir[k][1];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue; // 越界
if (grid[nr][nc] == 0 && !outside[nr][nc]) {
outside[nr][nc] = true;
qx[tail] = nr;
qy[tail] = nc;
tail++;
}
}
}
}
int main() {
// 按行优先读扁平整数：真实数据里有测例只有 9 行，缺的位置保持 0，不影响答案
for (int i = 0; i < N * N; i++)
scanf("%d", &grid[i / N][i % N]);
bfs_fill();
// 剩下没被染成外部的 0 格，就是被 * 围住的内部点，个数即面积
int ans = 0;
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (grid[r][c] == 0 && !outside[r][c])
ans++;
printf("%d\n", ans);
return 0;
}