为了帮助你构建 OJ 测试数据，我编写了一个完整的数据生成器。它包含了标准多源 BFS 参考解法（用于生成 .out）和针对性数据构造逻辑（用于生成 .in）。

虽然原题数据范围较小 ($10 \times 10$)，但我们在生成器中通过构造特定的“长链结构”和“孤岛结构”来确保能检测出代码逻辑的细微错误。

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

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>

using namespace std;

// --- 标准多源 BFS 解法，用于生成正确答案 ---
int solve_std(int m, int n, vector<vector<int>> grid) {
    struct Node { int r, c, t; };
    queue<Node> q;
    int fresh = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j, 0});
            else if (grid[i][j] == 1) fresh++;
        }
    }
    if (fresh == 0) return 0;
    int max_t = 0;
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        max_t = max(max_t, cur.t);
        for (int i = 0; i < 4; i++) {
            int nr = cur.r + dr[i], nc = cur.c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                grid[nr][nc] = 2;
                fresh--;
                q.push({nr, nc, cur.t + 1});
            }
        }
    }
    return (fresh == 0) ? max_t : -1;
}

// --- 数据写入与结果比对 ---
void make_test_case(int id, int m, int n, const vector<vector<int>>& grid) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    ofstream fout(in_name);
    fout << m << " " << n << "\n";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            fout << grid[i][j] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    fout.close();

    ofstream fans(out_name);
    fans << solve_std(m, n, grid) << endl;
    fans.close();
    cout << "Test Case " << id << " Generated (Size: " << m << "x" << n << ")" << endl;
}

int main() {
    mt19937 rng(time(0));

    // Case 1: 1x1 只有一个新鲜橘子 (边界条件: 无法腐烂)
    make_test_case(1, 1, 1, {{1}});

    // Case 2: 1x1 只有一个腐烂橘子 (边界条件: 0分钟)
    make_test_case(2, 1, 1, {{2}});

    // Case 3: 1x2 样例3 (边界条件: 有空位和腐烂，无新鲜)
    make_test_case(3, 1, 2, {{0, 2}});

    // Case 4: 3x3 样例1 (标准传播)
    make_test_case(4, 3, 3, {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}});

    // Case 5: 3x3 样例2 (无法到达新鲜橘子)
    make_test_case(5, 3, 3, {{2, 1, 1}, {0, 1, 1}, {1, 0, 1}});

    // Case 6: 10x10 全新鲜 (无腐烂源)
    {
        vector<vector<int>> g(10, vector<int>(10, 1));
        make_test_case(6, 10, 10, g);
    }

    // Case 7: 10x10 蛇形长链 (测试 BFS 最大深度)
    {
        vector<vector<int>> g(10, vector<int>(10, 0));
        for(int i=0; i<10; i++) {
            if(i%2==0) for(int j=0; j<10; j++) g[i][j]=1;
            else {
                if((i/2)%2==0) g[i][9]=1;
                else g[i][0]=1;
            }
        }
        g[0][0] = 2; // 起点腐烂
        make_test_case(7, 10, 10, g);
    }

    // Case 8: 10x10 四角腐烂 (多源同步搜索)
    {
        vector<vector<int>> g(10, vector<int>(10, 1));
        g[0][0] = g[0][9] = g[9][0] = g[9][9] = 2;
        make_test_case(8, 10, 10, g);
    }

    // Case 9: 10x10 随机中等密度
    {
        int m = 10, n = 10;
        vector<vector<int>> g(m, vector<int>(n));
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++) {
                int r = rng() % 100;
                if (r < 10) g[i][j] = 2;      // 10% 腐烂
                else if (r < 80) g[i][j] = 1; // 70% 新鲜
                else g[i][j] = 0;             // 20% 空
            }
        make_test_case(9, m, n, g);
    }

    // Case 10: 10x10 极端分布 (孤岛+密集)
    {
        int m = 10, n = 10;
        vector<vector<int>> g(m, vector<int>(n, 1));
        for(int i=0; i<m; i++) g[i][5] = 0; // 中间切断
        g[0][0] = 2; // 只有左边有腐烂
        make_test_case(10, m, n, g);
    }

    return 0;
}

测试数据设计逻辑说明

1. 覆盖边界情况：
   • Case 1-3：针对 $1 \times 1$ 或 $1 \times 2$ 这种极小规模数据，测试程序是否能正确处理“无新鲜橘子”或“无法传染”的特例。
2. 验证算法效率与深度：
   • Case 7 (蛇形长链)：这是经典的 BFS 测试数据。在这种结构下，传播是线性的，时间（分钟）会达到最大值。如果选手误用了错误的 DFS 或者逻辑不严谨，容易在这里出错。
3. 多源同步验证：
   • Case 8 (四角腐烂)：专门测试“多源”特性。如果选手错误地对每个源点跑一遍独立的 BFS 并没有取正确的最小值，则会出错。
4. 文件大小控制：
   • 由于 $M, N \le 10$，单个 .in 文件内容极少（约 200 字节）。10 个测试点总大小不到 10 KB，完全符合 2MB 的要求，极大节省了 OJ 评测机的磁盘 IO 压力。
5. 安全性：
   • 生成器内部解法采用迭代式 BFS，非递归，确保在生成数据时自身不会爆栈。
   • 所有随机数使用 mt19937，保证了分布的均匀性。

如何使用

1. 复制上述代码并在 C++ 环境下编译运行。
2. 它会在程序运行目录下自动生成 1.in 到 10.out 的全部文件。
3. 将这些文件打包即可上传至你的 NOI 模拟赛评测系统。

在 NOI 竞赛中，处理“扩散”、“传染”或“最短时间”类问题，通常有两条路：模拟（适合小数据或启发思考）和 BFS（正解）。

以下是从暴力模拟到最优多源 BFS 的演进过程。

版本一：暴力模拟法 (Simulation)

思路： 每一分钟扫描一遍整个矩阵。如果发现一个橘子是腐烂的（2），就尝试传染它周围的橘子。 注意： 为了防止“同一分钟内连续传染”（即 A 传染 B，B 立即在同一分钟传染 C），我们需要开一个备份数组，或者标记哪些橘子是“新腐烂”的。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int m, n;
int grid[15][15];
int temp[15][15]; // 辅助数组，记录下一分钟的状态

int main() {
    cin >> m >> n;
    int fresh = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 1) fresh++;
        }
    }

    if (fresh == 0) { cout << 0 << endl; return 0; }

    int minutes = 0;
    while (true) {
        bool changed = false;
        // 复制当前状态到 temp
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) temp[i][j] = grid[i][j];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) { // 如果是腐烂的
                    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dx[k], nj = j + dy[k];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                            if (temp[ni][nj] != 2) {
                                temp[ni][nj] = 2; // 变为腐烂
                                fresh--;
                                changed = true;
                            }
                        }
                    }
                }
            }
        }

        if (!changed) break; // 这一分钟没有新橘子腐烂，停止

        // 更新原数组
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) grid[i][j] = temp[i][j];
        
        minutes++;
    }

    if (fresh > 0) cout << -1 << endl;
    else cout << minutes << endl;

    return 0;
}

• 时间复杂度：$O((M \times N) \times (M \times N))$。每分钟扫描 $O(MN)$，最多扫描 $O(MN)$ 分钟。
• 空间复杂度：$O(M \times N)$。

版本二：多源 BFS (Standard Multi-source BFS)

思路： 暴力模拟之所以慢，是因为我们每分钟都要扫描很多“根本不会变”的空格或已经腐烂很久的橘子。 优化： 只有“刚刚变腐烂”的橘子才有能力在下一分钟传染别人。我们将所有初始腐烂的橘子同时放入队列，这就是多源 BFS。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 坐标结构体
struct Node {
    int r, c, t; // 行、列、当前时间
};

int main() {
    int m, n;
    if (!(cin >> m >> n)) return 0;

    int grid[15][15];
    queue<Node> q;
    int fresh = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 2) {
                q.push({i, j, 0}); // 初始腐烂橘子，时间为 0
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }

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

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        max_time = max(max_time, curr.t);

        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dx[i];
            int nc = curr.c + dy[i];

            // 越界检查且必须是新鲜橘子
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                grid[nr][nc] = 2; // 传染
                fresh--;
                q.push({nr, nc, curr.t + 1}); // 下一分钟传染源
            }
        }
    }

    // 关键点：最后检查是否还有新鲜橘子
    if (fresh > 0) cout << -1 << endl;
    else cout << max_time << endl;

    return 0;
}

• 时间复杂度：$O(M \times N)$。每个点只进队一次。
• 空间复杂度：$O(M \times N)$。

版本三：最优复杂度版 (Layered BFS)

思路： 在 NOI 竞赛中，有时为了节省内存或提高常数效率，我们不把 time 存进结构体，而是采用“按层剥离”的方法。这样队列里只需要存坐标。

#include <iostream>
#include <queue>

using namespace std;

int grid[15][15];
int m, n;

int solve() {
    // pair<int, int> 比较常用，first存r, second存c
    queue<pair<int, int>> q;
    int fresh = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    }

    if (fresh == 0) return 0;

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

    while (!q.empty()) {
        int sz = q.size(); // 当前分钟内的所有腐烂橘子数
        bool rotted_any = false;

        for (int i = 0; i < sz; i++) {
            pair<int, int> curr = q.front();
            q.pop();

            for (int k = 0; k < 4; k++) {
                int nr = curr.first + dx[k];
                int nc = curr.second + dy[k];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    q.push({nr, nc});
                    rotted_any = true; // 标记这一分钟确实传染了人
                }
            }
        }
        if (rotted_any) minutes++;
    }

    return (fresh == 0) ? minutes : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    while (cin >> m >> n) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) cin >> grid[i][j];
        cout << solve() << endl;
    }
    return 0;
}

复杂度分析思考过程

1. 时间复杂度：

   • 初始化扫描一遍矩阵：$O(MN)$。
   • BFS 过程中，每个格子（橘子）只有三种状态：空、新鲜、腐烂。
   • 一个新鲜橘子只会变腐烂一次，变腐烂后入队一次，出队一次。
   • 出队时检查 4 个方向，常数级操作。
   • 结论：总时间复杂度为 $O(MN)$。对于题目给定的 $10 \times 10$，简直是瞬间完成。

2. 空间复杂度：

   • grid 数组：$O(MN)$。
   • queue 队列：最坏情况下（全部是橘子且同时腐烂一半）空间为 $O(MN)$。
   • 结论：总空间复杂度 $O(MN)$。

时间复杂度优化建议 (NOI 进阶)

• 位运算优化：如果 $M, N$ 非常大且只有 0 和 1（类似于此题的变种），可以使用 std::bitset 进行行级同步操作。
• 输入输出优化：虽然本题数据极小，但在 NOI 中遇到 $10^6$ 级别数据，必须使用 scanf 或 getchar() 版本的快读。
• 原地标记：本题已经在 grid 上直接将 1 改为 2，这避免了额外的 visited 数组，是空间优化的典型手段。

读题关键词在哪里？

1. “相邻 ... 4个方向”：确认为网格图搜索，方向数组大小为 4。
2. “每分钟 ... 发生接触”：这是典型的 BFS 层级递进 信号。
3. “最少分钟数”：最短路径/最短时间问题，首选 BFS。
4. “如果不满足 ... 输出 -1”：说明图可能不连通，需要最后检查 fresh 计数器或遍历地图。
5. 多个初始腐烂橘子：这是 “多源” 的核心特征，所有源点必须第一批入队。