你好！作为金牌教练，我为你准备了一个高效、稳健的全自动测试数据生成器。

该生成器采用 C++14 标准，内部集成了基于 BFS（广度优先搜索） 的标准解法来生成 .out 文件。BFS 的选择是为了确保在处理复杂连通块（如长蛇形岛屿）时，生成器本身不会因为递归过深而崩溃。

数据生成器设计思路

1. 覆盖范围：

   • Case 1-2: 最小边界条件（$1 \times 1$, $2 \times 2$）。
   • Case 3: 全陆地（$0$ 填充），预期结果为 $0$。
   • Case 4: 全水域（$1$ 填充），预期结果为 $0$。
   • Case 5: 棋盘格布局（陆地互不相连），测试基础统计能力。
   • Case 6: 巨大的环形岛屿（中间包围着水和另一个小岛），测试嵌套判断。
   • Case 7-8: 稀疏与稠密随机图（$100 \times 100$）。
   • Case 9: 蛇形长路径陆地（从边缘延伸至中心），测试搜索的完整性。
   • Case 10: 极限综合测试点。

2. 性能与安全：

   • 空间：$100 \times 100$ 的矩阵加上空格，每个文件约 20KB，10 组数据总计约 200KB，远小于 2MB。
   • 防爆栈：solve 过程使用 std::queue 实现 BFS。
   • 鲁棒性：处理了 $M, N$ 为 1 的边界情况，无除零风险。

数据生成器完整代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

// --- 内部标程：使用 BFS 规避递归风险 ---
int solve(int M, int N, vector<vector<int>>& grid) {
    if (M <= 2 || N <= 2) return 0; // 边界点必然触碰边缘，不可能有封闭岛屿

    // 1. 将所有触碰边界的陆地(0)及其连通部分标记为水(1)
    auto bfs_fill = [&](int sx, int sy) {
        if (grid[sx][sy] == 1) return;
        queue<pair<int, int>> q;
        q.push({sx, sy});
        grid[sx][sy] = 1;
        int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
        while (!q.empty()) {
            pair<int, int> cur = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = cur.first + dx[i], ny = cur.second + dy[i];
                if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
    };

    // 淹没边缘
    for (int i = 0; i < M; i++) {
        bfs_fill(i, 0); bfs_fill(i, N - 1);
    }
    for (int j = 0; j < N; j++) {
        bfs_fill(0, j); bfs_fill(M - 1, j);
    }

    // 2. 统计剩下的封闭陆地连通块
    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                count++;
                bfs_fill(i, j);
            }
        }
    }
    return count;
}

// --- 数据生成逻辑 ---
void generate_test_case(int id) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    ofstream fin(in_file);
    ofstream fout(out_file);

    int M, N;
    // 设定不同规模
    if (id <= 2) { M = id; N = id; }
    else if (id <= 4) { M = 10; N = 10; }
    else { M = 100; N = 100; }

    vector<vector<int>> grid(M, vector<int>(N, 1));

    switch (id) {
        case 1: grid[0][0] = 0; break; 
        case 2: grid = {{0, 1}, {1, 0}}; break;
        case 3: // 全陆地
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = 0;
            break;
        case 4: // 全水域
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = 1;
            break;
        case 5: // 棋盘格
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = (i+j)%2;
            break;
        case 6: // 环形包围
            for(int i=2; i<M-2; i++) for(int j=2; j<N-2; j++) grid[i][j] = 0;
            for(int i=4; i<M-4; i++) for(int j=4; j<N-4; j++) grid[i][j] = 1;
            grid[M/2][N/2] = 0; // 中心一个封闭岛
            break;
        case 7: // 稀疏随机 (10% 陆地)
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) if(rand()%10 == 0) grid[i][j] = 0;
            break;
        case 8: // 稠密随机 (40% 陆地)
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) if(rand()%10 < 4) grid[i][j] = 0;
            break;
        case 9: // 蛇形路径 (触碰边界)
            for(int j=0; j<N-2; j++) grid[0][j] = 0;
            for(int i=0; i<M-2; i++) grid[i][N-3] = 0;
            break;
        case 10: // 复杂综合
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = rand()%2;
            break;
    }

    // 写入输入文件 (NOI 格式：空格分隔)
    fin << M << " " << N << "\n";
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            fin << grid[i][j] << (j == N - 1 ? "" : " ");
        }
        fin << "\n";
    }

    // 计算并写入输出文件
    int ans = solve(M, N, grid);
    fout << ans << "\n";

    fin.close();
    fout.close();
    cout << "Generated Case " << id << ": " << M << "x" << N << endl;
}

int main() {
    srand(time(0));
    for (int i = 1; i <= 10; i++) {
        generate_test_case(i);
    }
    cout << "All 10 test cases generated successfully." << endl;
    return 0;
}

教练的提示（针对 OJ 创建者）：

1. 数据校验：

   • 该生成器生成的 .in 文件采用了标准空格分隔格式，这是 NOIP/NOI 最常见的格式。
   • 1.in 为最小 $1 \times 1$ 情况，此时由于点本身就在边界，结果必然是 0。这是一个非常好的边界陷阱。

2. 评测环境建议：

   • 内存限制：设定为 128MB 或 256MB。
   • 时间限制：设定为 1.0s。本题 $O(MN)$ 算法在 $100 \times 100$ 下运行时间通常小于 1ms。
   • 栈空间：如果学生使用递归 DFS，请确保系统栈限制放开（在 Linux 评测机通常是 unlimited），否则对于 Case 9 或 Case 10 这种构造的长路径可能会发生段错误（RE）。

3. 读题陷阱提醒：

   • 由于本题 0 是陆地，1 是水，学生很容易在写 dfs 的终止条件时写反（习惯性地把 1 当作陆地）。
   • Case 6 设计了一个“岛中湖，湖中岛”的结构，能够有效检测那些处理边界逻辑不严谨的代码。

希望这套工具能帮你构建出一套高质量的 NOI 练习题！加油！

针对“封闭岛屿的数量”这一进阶题型，我将为你展示从“搜索时判断”到“预处理排除”的演进过程。在 NOI 竞赛中，逻辑的简洁性直接决定了你在高压环境下写出 Bug 的概率。

版本一：基础 DFS + 状态标记（直接搜索法）

这种思路最直观：对每个没访问过的陆地进行 DFS。在搜索过程中，只要该岛屿中有任意一个格子位于边界，这个岛屿就标记为“不封闭”。

复杂度分析：

• 时间复杂度： $O(M \times N)$。每个点只会被 vis 数组标记一次。
• 空间复杂度： $O(M \times N)$。递归深度最坏情况下为全图大小。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 105;
int grid[MAXN][MAXN];
bool vis[MAXN][MAXN];
int M, N;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 检查是否在边界上
bool isBoundary(int x, int y) {
    return x == 0 || x == M - 1 || y == 0 || y == N - 1;
}

// DFS 返回当前岛屿是否是封闭的
// 注意：即使发现了越界，也要继续搜完整个连通块，否则剩下的部分会被当成新岛屿
void dfs(int x, int y, bool &closed) {
    vis[x][y] = true;
    
    // 关键点：只要有一个点在边界，当前岛屿就不是封闭的
    if (isBoundary(x, y)) {
        closed = false;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 易错点：这里逻辑是 grid[nx][ny] == 0 代表陆地
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] == 0 && !vis[nx][ny]) {
            dfs(nx, ny, closed);
        }
    }
}

int main() {
    if (scanf("%d %d", &M, &N) != 2) return 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    int ans = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            // 发现未访问的陆地
            if (grid[i][j] == 0 && !vis[i][j]) {
                bool closed = true;
                dfs(i, j, closed);
                if (closed) ans++;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

版本二：先“淹没”边际陆地（最优解法：预处理排除法）

在 NOI 中，这种方法被公认为最稳健。核心逻辑： 既然碰到边界的岛屿不算，那我就先从四条边出发，把所有能碰到的陆地全部用 DFS 变成水。剩下的陆地必然是封闭的。

复杂度分析：

• 时间复杂度： $O(M \times N)$。两次扫描，效率极高。
• 空间复杂度： $O(M \times N)$。不需要额外的 vis 数组（原地修改）。

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 105;
int grid[MAXN][MAXN];
int M, N;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 纯填充函数：将连通的 0 全部变为 1
void fill(int x, int y) {
    if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] == 1) return;
    
    grid[x][y] = 1; // 淹没
    for (int i = 0; i < 4; i++) {
        fill(x + dx[i], y + dy[i]);
    }
}

int main() {
    if (scanf("%d %d", &M, &N) != 2) return 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) scanf("%d", &grid[i][j]);
    }

    // 第一步：淹没所有与边界相连的陆地
    for (int i = 0; i < M; i++) {
        if (grid[i][0] == 0) fill(i, 0);
        if (grid[i][N - 1] == 0) fill(i, N - 1);
    }
    for (int j = 0; j < N; j++) {
        if (grid[0][j] == 0) fill(0, j);
        if (grid[M - 1][j] == 0) fill(M - 1, j);
    }

    // 第二步：统计剩下孤立的岛屿
    int ans = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                ans++;
                fill(i, j); // 统计完一个就淹掉一个
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

版本三：BFS 迭代版本（大内存/深路径防御版）

当网格规模很大且可能存在极长路径时，为了防止 DFS 爆栈，在竞赛中常改用 BFS（手动模拟队列）。

复杂度分析：

• 时间复杂度： $O(M \times N)$。
• 空间复杂度： $O(\min(M, N))$，队列的宽度。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 105;
int grid[MAXN][MAXN];
int M, N;

void bfs_fill(int sx, int sy) {
    if (grid[sx][sy] == 1) return;
    
    queue<pair<int, int>> q;
    q.push({sx, sy});
    grid[sx][sy] = 1;
    
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i], ny = cur.second + dy[i];
            if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] == 0) {
                grid[nx][ny] = 1; // 易错点：入队时即标记，防止重复入队
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    scanf("%d %d", &M, &N);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++) scanf("%d", &grid[i][j]);

    // 依然使用预处理法，但改为 BFS 实现
    for (int i = 0; i < M; i++) {
        bfs_fill(i, 0); bfs_fill(i, N-1);
    }
    for (int j = 0; j < N; j++) {
        bfs_fill(0, j); bfs_fill(M-1, j);
    }

    int ans = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                ans++;
                bfs_fill(i, j);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

教练的复杂度优化建议与思考过程

1. 关于“原地修改”的艺术： 在 NOI 竞赛中，如果题目给定的数组可以直接修改，原地填充 (In-place Fill) 是最推荐的。它不仅节省了 $O(MN)$ 的辅助空间，更重要的是它减少了维护 vis 数组出错的可能性。

2. 时间复杂度优化建议：

   • I/O 挂： 如果 $M, N$ 达到 1000 以上，请使用 scanf。如果达到 2000 以上，考虑使用快读 inline int read()。
   • 常数优化： 在 fill 函数中，使用 if (grid[x][y]) return; 代替 if (grid[x][y] == 1) return; 并没有显著提升，真正的提升在于减少递归分支中的冗余判断。

3. 空间复杂度优化建议：

   • 栈空间溢出： 这是 DFS 的阿喀琉斯之踵。如果比赛环境（如 Windows 下的某些评测器）对栈空间有限制，务必在 main 函数开头尝试使用 std::vector 动态分配或改写为 BFS。
   • 位压缩： 本题数据只有 0 和 1，理论上可以用 bitset 存储，但这通常会增加代码复杂度，只有在内存限制极其苛刻（如 4MB）时才考虑。

4. 总结读题关键词：

   • 看到“封闭”，思考“补集”——即先处理掉所有不封闭的，剩下的就是答案。
   • 看到“岛屿”，思考“连通块”——即 DFS/BFS 的标准应用。

金牌教练点评： 版本二的代码逻辑最为简洁：先去边，再数数。 这种将复杂条件转化为简单预处理的思维，不仅适用于岛屿问题，也是解决很多高级图论问题的钥匙。加油！