P4898 围成面积（基础）

解题思路

第一步，读懂题目。 一张 10×10 的表格里只有 0 和 1。数字 1 围成了一个闭合的圈，我们要数一数圈里面（被 1 挡住、到不了外面）的 0 有多少个。样例里 1 围住了 15 个点，所以答案是 15。

第二步，换个思路：从外面"灌水"。 直接判断"哪些 0 在里面"不太好办，我们可以反过来：从表格最外面的边界开始，凡是能通过 0 一路走到外面的格子，肯定都不在圈里面。剩下那些"到不了外面"的 0，就是被 1 围住的部分。

第三步，加一圈安全边界。 把原来的 10×10 表格外面再包一圈 0，变成 12×12，这样从左上角 (0,0) 出发做 BFS，就能把"外部"的所有 0 都走到，而圈里面的 0 被 1 挡住走不到。

第四步，用 BFS 标记外部。 用一个队列从 (0,0) 开始向上下左右扩散，遇到 0 就把它标记成 2（表示外部可达），继续入队。1 是墙，不能走。BFS 结束后，数一数原来 10×10 范围内还有多少个 0 没有被标记成 2，这些就是被围住的面积。

边界情况： 如果表格边上就有 1，包上的一圈 0 保证水一定能从边界流进来。如果整个表格都没有 1，那所有 0 都被标记成 2，面积是 0。

参考代码

// 围成面积：外围加一圈0后从外部BFS,统计没被染到的内部0个数
#include <iostream>
using namespace std;

int g[12][12], cnt; // g[0..11]含外圈, 2标记外部可达
int qx[200], qy[200]; // BFS队列
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= 10; j++)
            cin >> g[i][j];
    int head = 0, tail = 0; // 从外圈(0,0)开始BFS
    qx[tail] = 0; qy[tail] = 0; tail++;
    g[0][0] = 2;
    while (head < tail) {
        int x = qx[head], y = qy[head]; head++;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx <= 11 && ny >= 0 && ny <= 11 && g[nx][ny] == 0) {
                g[nx][ny] = 2;
                qx[tail] = nx; qy[tail] = ny; tail++;
            }
        }
    }
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= 10; j++)
            if (g[i][j] == 0) cnt++; // 没被外部染到的0被围住
    cout << cnt << endl;
    return 0;
}

复杂度分析

表格固定是 12×12，BFS 最多走 144 个格子，所以时间复杂度是 O(1) 量级（常数很小），空间也只需要存一张 12×12 的表格。