你好！我是金牌教练。针对“子岛屿数量”这道题，数据生成器的核心挑战在于构造出具有包含关系的复杂连通块，同时要严防生成器本身在计算标程答案时爆栈。

为了符合 OJ 2MB 的文件体积建议，我将数据规模进行了分层设计。$500 \times 500$ 的矩阵如果带空格输出，单个文件约 1MB，因此我们只在最后两个压力测试点使用最大规模，其余点通过构造特殊结构（如蛇形、环形）来保证测试强度。

一、 数据生成器设计策略

1. 基础边界 (Test 1-2)：$1 \times 1$ 和 $2 \times 2$ 的极小矩阵。
2. 极端全集 (Test 3-4)：grid1 全水或全陆地，测试逻辑的鲁棒性。
3. 棋盘格 (Test 5)：构造最大数量的独立微型岛屿。
4. 长链结构 (Test 8)：构造长度达到 $10^5$ 级别的蛇形路径。如果选手使用 DFS 且未扩栈，此点必崩。
5. 嵌套构造 (Test 9)：在 grid1 的陆地内部精确放置 grid2 的陆地。
6. 大规模随机 (Test 10)：$500 \times 500$ 稠密随机数据。

二、 数据生成器代码 (C++14)

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

using namespace std;

// --- BFS 标程：用于生成 .out 文件，非递归规避爆栈 ---
int solve(int M, int N, vector<vector<int>> g1, vector<vector<int>> g2) {
    int count = 0;
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (g2[i][j] == 1) {
                bool is_sub = true;
                queue<pair<int, int>> q;
                q.push({i, j});
                g2[i][j] = 0;
                
                while (!q.empty()) {
                    pair<int, int> cur = q.front(); q.pop();
                    if (g1[cur.first][cur.second] == 0) is_sub = false;
                    
                    for (int k = 0; k < 4; k++) {
                        int nx = cur.first + dx[k], ny = cur.second + dy[k];
                        if (nx >= 0 && nx < M && ny >= 0 && ny < N && g2[nx][ny] == 1) {
                            g2[nx][ny] = 0;
                            q.push({nx, ny});
                        }
                    }
                }
                if (is_sub) count++;
            }
        }
    }
    return count;
}

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

    int M, N;
    // 控制规模以控制文件总体积
    if (id <= 2) { M = id; N = id; }
    else if (id <= 5) { M = 20; N = 20; }
    else if (id <= 8) { M = 100; N = 100; }
    else { M = 500; N = 500; }

    vector<vector<int>> g1(M, vector<int>(N, 0)), g2(M, vector<int>(N, 0));

    switch (id) {
        case 3: // g1全水，g2有陆地 -> 0
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) g2[i][j] = rand()%2;
            break;
        case 4: // g1全陆地，g2有陆地 -> g2岛屿数
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) { g1[i][j] = 1; g2[i][j] = rand()%2; }
            break;
        case 5: // 棋盘格构造
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) g2[i][j] = (i+j)%2, g1[i][j] = (i%2);
            break;
        case 8: // S型蛇形路径压力测试
            for(int i=0; i<M; i++){
                int row_land = (i % 4 == 0 || i % 4 == 2);
                for(int j=0; j<N; j++){
                    if(i % 4 == 0 && j < N-1) g2[i][j] = 1;
                    if(i % 4 == 1 && j == N-2) g2[i][j] = 1;
                    if(i % 4 == 2 && j > 0) g2[i][j] = 1;
                    if(i % 4 == 3 && j == 1) g2[i][j] = 1;
                    g1[i][j] = g2[i][j]; // 默认全包含
                }
            }
            g1[0][0] = 0; // 故意破环一个点，使整条蛇失效
            break;
        case 9: // 随机嵌套
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) {
                g1[i][j] = (rand()%100 < 60); // g1陆地较多
                if(g1[i][j]) g2[i][j] = (rand()%100 < 30); // g2在g1范围内生成
            }
            break;
        default: // 通用随机
            for(int i=0; i<M; i++) for(int j=0; j<N; j++) {
                g1[i][j] = rand()%2; g2[i][j] = rand()%2;
            }
    }

    // 写入文件
    fin << M << " " << N << "\n";
    for(auto &row : g1) {
        for(int j=0; j<N; j++) fin << row[j] << (j==N-1 ? "" : " ");
        fin << "\n";
    }
    for(auto &row : g2) {
        for(int j=0; j<N; j++) fin << row[j] << (j==N-1 ? "" : " ");
        fin << "\n";
    }

    // 计算答案
    fout << solve(M, N, g1, g2) << endl;

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

int main() {
    srand(time(0));
    for (int i = 1; i <= 10; i++) make_data(i);
    return 0;
}

三、 测试点详细说明（创建 OJ 时参考）

1. Test 1-4 (边界与特殊逻辑)：
   • 主要通过极小规模和全 0/1 矩阵，排除代码中初始值错误或逻辑判断顺序有误的程序。
2. Test 5 (最大连通块数)：
   • 通过棋盘格产生大量面积为 1 的小岛。如果选手使用不恰当的 vis 数组或重复搜索，会产生性能损耗。
3. Test 8 (蛇形路径 - 关键点)：
   • 本测试点在 $100 \times 100$ 规模下构造了一条单向连通路径。
   • 考察点：如果选手使用 DFS 且没有开启 ulimit -s unlimited，或者递归写法不够精炼（如携带了太多局部变量），此点大概率会 Segmentation Fault。
4. Test 9-10 (大规模复杂判定)：
   • $500 \times 500$ 矩阵。
   • 文件大小：由于包含两个 $500 \times 500$ 的矩阵且带空格，单个文件约 1.2MB。
   • 运行效率：$O(MN)$ 算法对此规模的处理时间应在 $10ms \sim 50ms$ 之间。如果选手算法复杂度达到 $O((MN)^2)$ 或搜索存在大量冗余，此点必 TLE。

四、 读题关键词与坑点总结

• “子岛屿”判定顺序：一定要先找遍 grid2 的一个岛，确认其中每一个点在 grid1 是否都是陆地。
• 空间布局：矩阵 grid1 和 grid2 之后各自紧跟 $M \times N$ 的数据，读取时不要混淆。
• 内存优化：在处理 $500 \times 500$ 规模时，建议直接原地修改 grid2 数组（沉岛）来作为访问标记，节省一个 bool 数组的空间。

教练点评： 这套数据能完美区分出“只会搜”和“会高效、稳定地搜”的选手。特别是 Test 8 的蛇形数据，是区分 DFS 选手和 BFS/扩栈 DFS 选手的试金石。祝你的 OJ 建设顺利！加油！

你好！我是教练。这道题在 NOI 竞赛中非常经典，它考察的是复合图论条件判断。我们将通过三个版本，从最直观的“边搜边判”过渡到竞赛中最推荐的“预处理剔除法”。

版本一：基础 DFS + 状态标志位（直观暴力版）

这个版本的思路是：扫描 grid2，每发现一个岛屿，就用 DFS 把它完整走一遍。在走的过程中，检查每一个格子在 grid1 中是否也是陆地。

复杂度分析：

• 时间复杂度：$O(M \times N)$。每个点只会被 grid2 的 DFS 访问一次。
• 空间复杂度：$O(M \times N)$。递归栈深度在最坏情况下（如蛇形岛屿）为 $M \times N$。对于 $500 \times 500 = 2.5 \times 10^5$，在默认栈空间较小的环境下有 RTE (爆栈) 风险。

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 505;
int g1[MAXN][MAXN], g2[MAXN][MAXN];
int M, N;

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

// DFS 返回：当前搜索的连通块是否全部在 grid1 中也是陆地
bool dfs(int x, int y) {
    // 关键点：即使发现当前格子在 g1 中是水，也要继续搜完整个 g2 连通块
    // 否则剩下的 g2 陆地会被当成新的岛屿误判
    bool is_ok = true;
    if (g1[x][y] == 0) is_ok = false;

    g2[x][y] = 0; // 沉岛，标记已访问

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < M && ny >= 0 && ny < N && g2[nx][ny] == 1) {
            // 易错点：不能直接 return is_ok && dfs(...)，因为逻辑短路会导致后面的岛屿没被淹没
            if (!dfs(nx, ny)) is_ok = false;
        }
    }
    return is_ok;
}

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", &g1[i][j]);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++) scanf("%d", &g2[i][j]);

    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (g2[i][j] == 1) {
                if (dfs(i, j)) count++;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

版本二：BFS 迭代版（稳定性防御版）

针对 $500 \times 500$ 且可能存在长路径的数据，使用 std::queue 实现 BFS 可以利用堆内存，规避系统栈溢出的风险。

复杂度分析：

• 时间复杂度：$O(M \times N)$。
• 空间复杂度：$O(M \times N)$。队列存储空间。

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

using namespace std;

const int MAXN = 505;
int g1[MAXN][MAXN], g2[MAXN][MAXN];
int M, N;

bool bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    g2[sx][sy] = 0;
    
    bool is_sub = true;
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        // 核心判定：只要有一个点在 grid1 中是水，该岛屿就不是子岛屿
        if (g1[cur.first][cur.second] == 0) is_sub = false;

        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 && g2[nx][ny] == 1) {
                g2[nx][ny] = 0;
                q.push({nx, ny});
            }
        }
    }
    return is_sub;
}

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

    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (g2[i][j] == 1) {
                if (bfs(i, j)) count++;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

版本三：预处理剔除法（最优思维版）

这是教练最推荐的版本。逆向思考： 什么样的 grid2 岛屿肯定不是子岛屿？ 答：包含“污染点”（即 grid2[i][j]==1 但 grid1[i][j]==0）的岛屿。

解题节奏：

1. 先处理所有“污染点”，把它们所在的岛屿全部“淹没”。
2. 剩下的 grid2 陆地必然全部落在 grid1 的陆地范围内。
3. 统计剩下多少个连通块。

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 505;
int g1[MAXN][MAXN], g2[MAXN][MAXN];
int M, N;

void fill(int x, int y) {
    if (x < 0 || x >= M || y < 0 || y >= N || g2[x][y] == 0) return;
    g2[x][y] = 0;
    fill(x + 1, y); fill(x - 1, y);
    fill(x, y + 1); fill(x, y - 1);
}

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

    // 第一步：排除法。如果 g2 是陆地但 g1 是水，淹没该岛
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (g2[i][j] == 1 && g1[i][j] == 0) {
                fill(i, j);
            }
        }
    }

    // 第二步：统计。此时 g2 剩下的陆地全是合法的子岛屿
    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (g2[i][j] == 1) {
                count++;
                fill(i, j);
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

时间复杂度优化建议与思考过程

1. 关于递归深度优化： 在版本三中，如果担心爆栈，可以使用 std::vector<pair<int, int>> 手动模拟栈。在 NOI 竞赛中，如果 $500 \times 500$ 的数据被构造为极窄长链，DFS 会面临巨大压力。
2. 常数优化：
   • 使用 scanf 代替 cin 可提升 3-5 倍读入速度。
   • fill 函数中使用方向数组循环虽然代码美观，但手动展开 fill(x+1, y)... 四个方向在某些编译器下有微弱性能提升。
3. 合并逻辑： 虽然版本三是两遍扫描，但每遍扫描中每个格子最多处理一次。逻辑上的清晰降低了编写 Bug 的概率，这种“空间换逻辑”在竞赛中是值得的。

读题关键词总结

• “所有单元格” (Every cell)：这提示我们要进行全称命题判定。处理全称命题最快的方法通常是寻找反例。
• “子岛屿” (Sub Islands)：暗示了包含关系（Set Inclusion）。
• “两个矩阵”：提示这是一个双图比对问题，可能需要先对其中一张图做变换或预处理。

教练点评： 版本三展示了 OI 竞赛中非常重要的“模型简化”思想。通过第一遍扫描，我们将复杂的“包含判定”转化为了基础的“连通块计数”。这种思维跳跃是区分金牌选手与普通选手的关键。加油！