这是一个功能完备的 C++ 数据生成器。它集成了标准的BFS+Set去重解题逻辑（用于生成 .out 文件）和针对题目三个子任务及特殊边界情况设计的图形构造逻辑（用于生成 .in 文件）。

运行此代码将自动在当前目录下生成 1.in/1.out 到 10.in/10.out。

数据生成策略

为了全面测试代码的正确性和鲁棒性，设计了以下 10 个测试点：

1. 极小数据 ($5 \times 6$)：基础逻辑测试。
2. 全图同色 ($20 \times 20$)：只有一个巨大的连通块，答案应为 1。
3. 全图不同色 ($20 \times 20$)：每个点颜色都不同，有 400 个连通块，但形状全是 $1 \times 1$，答案应为 1。
4. 横条纹 (Subtask 2)：每行颜色不同，形成 $N$ 个 $1 \times M$ 的长条。答案应为 1。
5. 竖条纹 (Subtask 2)：每列颜色不同，形成 $M$ 个 $N \times 1$ 的长条。答案应为 1。
6. 棋盘格 ($500 \times 500$)：相邻格子颜色不同。形成 250,000 个 $1 \times 1$ 的块。测试大数据下的性能和去重（答案应为 1）。
7. 俄罗斯方块印章 ($100 \times 100$)：随机在地图上“盖章”标准的俄罗斯方块形状（T型、L型等），使用不同颜色。测试“不同颜色但形状相同视为同类”的逻辑。
8. 不同大小矩形 ($100 \times 100$)：生成很多不同长宽的矩形，测试一般去重逻辑。
9. 随机噪声 ($50 \times 50$)：完全随机颜色，测试一般连通性。
10. 极限随机 ($500 \times 500$)：大数据随机，压力测试。

C++ 数据生成器代码

/**
 * P10379 [GESP202403 七级] 俄罗斯方块 - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
namespace Solution {
    const int MAXN = 505;
    int n, m;
    int grid[MAXN][MAXN];
    bool vis[MAXN][MAXN];
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    void bfs(int sx, int sy, set<vector<pair<int, int>>>& shapes) {
        int color = grid[sx][sy];
        vector<pair<int, int>> shape;
        queue<pair<int, int>> q;
        q.push({sx, sy});
        vis[sx][sy] = true;
        int min_x = sx, min_y = sy;

        while (!q.empty()) {
            pair<int, int> curr = q.front();
            q.pop();
            shape.push_back(curr);
            min_x = min(min_x, curr.first);
            min_y = min(min_y, curr.second);

            for (int i = 0; i < 4; i++) {
                int nx = curr.first + dx[i];
                int ny = curr.second + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                    if (!vis[nx][ny] && grid[nx][ny] == color) {
                        vis[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
        }
        for (auto &p : shape) {
            p.first -= min_x;
            p.second -= min_y;
        }
        sort(shape.begin(), shape.end());
        shapes.insert(shape);
    }

    int solve(int _n, int _m, const vector<vector<int>>& _grid) {
        n = _n; m = _m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                grid[i][j] = _grid[i][j];
                vis[i][j] = false;
            }

        set<vector<pair<int, int>>> shapes;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!vis[i][j]) {
                    bfs(i, j, shapes);
                }
            }
        }
        return shapes.size();
    }
}

// ==========================================
// Part 2: 数据构造逻辑 (生成 .in)
// ==========================================
int randInt(int min, int max) {
    return rand() % (max - min + 1) + min;
}

// 基础形状定义 (相对坐标)
const vector<vector<pair<int,int>>> TETRIS_SHAPES = {
    {{0,0}, {0,1}, {1,0}, {1,1}},       // O (2x2 square)
    {{0,0}, {0,1}, {0,2}, {0,3}},       // I (Horizontal)
    {{0,0}, {1,0}, {2,0}, {3,0}},       // I (Vertical)
    {{0,1}, {1,0}, {1,1}, {1,2}},       // T
    {{0,0}, {1,0}, {2,0}, {2,1}},       // L
    {{0,0}, {0,1}, {1,1}, {1,2}}        // S
};

void makeData(int id) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N, M;
    vector<vector<int>> grid;

    // -------------------------------------------------
    // Subtask 1: 小数据
    // -------------------------------------------------
    if (id == 1) {
        N = 5; M = 6;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = randInt(1, 10);
    }
    else if (id == 2) {
        // 全图同色 (1种形状)
        N = 20; M = 20;
        grid.assign(N + 1, vector<int>(M + 1, 1));
    }
    else if (id == 3) {
        // 全图不同色 (400个 1x1 连通块 -> 1种形状)
        N = 20; M = 20;
        grid.assign(N + 1, vector<int>(M + 1));
        int cnt = 0;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = ++cnt;
    }
    // -------------------------------------------------
    // Subtask 2: 只有 1xX 或 Xx1 (长条)
    // -------------------------------------------------
    else if (id == 4) {
        // 横条纹 (每行颜色不同)
        N = 50; M = 50;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = i; // 第i行全是颜色i
    }
    else if (id == 5) {
        // 竖条纹 (每列颜色不同)
        N = 50; M = 50;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = j; // 第j列全是颜色j
    }
    // -------------------------------------------------
    // Subtask 3 & 综合测试: 大数据
    // -------------------------------------------------
    else if (id == 6) {
        // 棋盘格 (500x500): 25万个 1x1，测试性能
        N = 500; M = 500;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = (i + j) % 2 + 1;
    }
    else if (id == 7) {
        // 随机印章: 在空白地图上随机盖俄罗斯方块
        // 重点测试: 不同颜色但形状相同的去重逻辑
        N = 100; M = 100;
        grid.assign(N + 1, vector<int>(M + 1, 0)); // 0为背景色
        int stamp_cnt = 2000;
        int color_cnt = 1;
        while(stamp_cnt--) {
            int type = randInt(0, TETRIS_SHAPES.size() - 1);
            int r = randInt(1, N - 4);
            int c = randInt(1, M - 4);
            int my_color = ++color_cnt; // 每次用新颜色，测试形状去重
            
            bool ok = true;
            // 检查冲突
            for(auto p : TETRIS_SHAPES[type]) {
                if(grid[r + p.first][c + p.second] != 0) ok = false;
            }
            // 填入
            if(ok) {
                for(auto p : TETRIS_SHAPES[type]) {
                    grid[r + p.first][c + p.second] = my_color;
                }
            }
        }
        // 填充背景0为不同颜色，避免巨大的背景连通块干扰
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if(grid[i][j] == 0) grid[i][j] = ++color_cnt;
    }
    else if (id == 8) {
        // 矩形工厂: 生成随机大小的矩形
        N = 100; M = 100;
        grid.assign(N + 1, vector<int>(M + 1, 0));
        int color = 0;
        for(int i=1; i<=N; i+=randInt(2, 10)) {
            for(int j=1; j<=M; j+=randInt(2, 10)) {
                color++;
                int h = randInt(1, 5);
                int w = randInt(1, 5);
                for(int x=0; x<h && i+x<=N; x++)
                    for(int y=0; y<w && j+y<=M; y++)
                        grid[i+x][j+y] = color;
            }
        }
        // 填补空隙
         for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if(grid[i][j] == 0) grid[i][j] = ++color;
    }
    else if (id == 9) {
        // 小规模随机噪声
        N = 50; M = 50;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = randInt(1, 5); // 颜色少，容易形成随机形状
    }
    else { // id == 10
        // 极限规模随机噪声
        N = 500; M = 500;
        grid.assign(N + 1, vector<int>(M + 1));
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                grid[i][j] = randInt(1, 20);
    }

    // 写入输入
    fin << N << " " << M << endl;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            fin << grid[i][j] << (j == M ? "" : " ");
        }
        fin << endl;
    }

    // 计算并写入输出
    int ans = Solution::solve(N, M, grid);
    fout << ans << endl;

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

int main() {
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    cout << "All done!" << endl;
    return 0;
}

你好！作为OI教练，我为你整理了这道 GESP 七级真题《俄罗斯方块》的标准题解代码、详细注释以及复杂度分析。

核心解题思路回顾

1. 提取连通块：使用 BFS（广度优先搜索） 遍历网格，找到所有同色且四连通的方块集合。
2. 形状标准化（归一化）：
   • 相对坐标：为了让形状与位置无关，需要找到该连通块的“左上角锚点”（即所有点中最小的行号 min_x 和最小的列号 min_y）。
   • 平移：将连通块内所有点的坐标 $(x, y)$ 转换为 $(x - min\_x, y - min\_y)$。
3. 形状唯一化（Canonicalization）：
   • 由于 BFS 的搜索顺序可能不同，得到的坐标列表顺序不固定。必须对归一化后的坐标列表进行 排序，使其成为该形状唯一的“身份证”。
4. 去重统计：
   • 使用 std::set 存储这些“身份证”。set 会自动根据 vector 的内容去重。最后输出集合的大小。

标准题解代码 (C++14 NOIP标准)

/**
 * 题目：P10379 [GESP202403 七级] 俄罗斯方块
 * 算法：BFS/DFS + 坐标归一化 + STL Set去重
 * 难度：普及+/提高-
 */

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // 用于 sort
#include <set>       // 用于去重

using namespace std;

// 定义最大范围，500*500
const int MAXN = 505;

// 网格数据与访问标记
int n, m;
int grid[MAXN][MAXN];
bool vis[MAXN][MAXN];

// 方向数组：上、下、左、右
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 存储所有唯一的形状
// 一个形状就是一个坐标列表 vector<pair<int,int>>
set<vector<pair<int, int>>> distinct_shapes;

/**
 * BFS 搜索连通块并提取形状
 * (sx, sy): 搜索起点
 */
void bfs(int sx, int sy) {
    // 1. 初始化
    int color = grid[sx][sy];
    vector<pair<int, int>> shape; // 用于存储当前连通块的坐标
    queue<pair<int, int>> q;
    
    q.push({sx, sy});
    vis[sx][sy] = true;
    
    // 2. 维护包围盒的左上角 (min_x, min_y) 用于归一化
    // 易错点1: 不要直接用 sx, sy 作为减数，因为起点不一定是形状的最左上角
    int min_x = sx, min_y = sy;
    
    // 3. 开始搜索
    while(!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        
        int cx = curr.first;
        int cy = curr.second;
        
        // 记录坐标并更新边界
        shape.push_back({cx, cy});
        min_x = min(min_x, cx);
        min_y = min(min_y, cy);
        
        // 拓展 4 个方向
        for(int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 越界判断
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                // 如果未访问且颜色相同，则是同一个连通块
                if(!vis[nx][ny] && grid[nx][ny] == color) {
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
    
    // 4. 坐标归一化 (Normalization)
    // 将所有点平移，使得形状的左上角对齐到 (0,0)
    for(auto &p : shape) {
        p.first -= min_x;
        p.second -= min_y;
    }
    
    // 5. 序列排序 (Canonicalization)
    // 易错点2: 必须排序！因为 vector 的比较是按顺序逐个比较的。
    // 如果不排序，{(0,0), (1,1)} 和 {(1,1), (0,0)} 会被当成不同的形状。
    sort(shape.begin(), shape.end());
    
    // 6. 存入 Set 去重
    distinct_shapes.insert(shape);
}

void solve() {
    // IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    if(!(cin >> n >> m)) return;
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 遍历全图寻找连通块
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!vis[i][j]) {
                bfs(i, j);
            }
        }
    }
    
    cout << distinct_shapes.size() << endl;
}

int main() {
    solve();
    return 0;
}

复杂度分析与思考过程

1. 时间复杂度分析

• 搜索部分：
  • BFS 会访问每个格子一次，且仅一次。
  • 总时间为 $O(N \times M)$。
• 形状处理部分：
  • 设总点数为 $S = N \times M$。
  • 设发现了 $K$ 个连通块，第 $i$ 个连通块的大小为 $S_i$，则 $\sum S_i = S$。
  • 排序：第 $i$ 个形状排序耗时 $O(S_i \log S_i)$。总耗时 $\sum (S_i \log S_i) \le S \log S$。
  • Set 插入：std::set 基于红黑树。插入长度为 $L$ 的 vector，比较的时间复杂度为 $O(L)$。
    • 插入耗时为 $O(S_i \times \log(\text{当前集合大小})) \le O(S_i \times \log K)$。
    • 总插入耗时 $\sum (S_i \log K) = S \log K$。
• 总复杂度：
  • 最坏情况 $O(NM \log(NM))$。
  • 代入数据 $N, M \le 500$， $NM = 2.5 \times 10^5$。
  • 计算量级约为 $10^6 \sim 10^7$ 次运算，远小于 C++ 1秒限时通常能处理的 $10^8$ 次运算。完全可以通过。

2. 空间复杂度分析

• grid 和 vis 数组：$O(NM)$。
• distinct_shapes (Set)：在最坏情况下（例如棋盘格，所有点互不连通，或者所有形状都不同），可能需要存储接近 $O(NM)$ 个点。
• 总空间：$O(NM)$。
• $500 \times 500$ 的 int 约为 1MB，内存限制通常是 128MB+，空间非常充裕。

进一步优化的思考 (针对更大数据范围)

如果 $N, M$ 增大到 $2000$ 或者时限更紧，std::set<vector> 的常数可能会导致超时，可以考虑以下优化：

1. 字符串哈希 (String Hashing) / 多项式哈希：

   • 将归一化并排序后的坐标序列 $\{(x_1, y_1), (x_2, y_2)...\}$ 视为一个字符串或序列。
   • 计算其 Hash 值（例如 hash = hash * BASE + x; hash = hash * BASE + y;）。
   • 将 vector<pair> 的比较 $O(S_i)$ 降级为整数比较 $O(1)$。
   • 为了防冲突，可以使用双哈希（Double Hash）。

2. 最小表示法：

   • 对于形状的存储，其实不需要存储完整的坐标序列。
   • 如果是简单的俄罗斯方块（4格），可以直接将 $4 \times 4$ 的 01 矩阵压缩成一个 long long 整数进行存储和比较。但这道题连通块大小不固定，此法不适用。

对于本题的 GESP 七级难度和数据范围，上述的标准 STL 解法是最稳妥、编码最快且不易出错的选择。

你好！我是你的OI教练。很高兴带你挑战这道 GESP 七级的题目《俄罗斯方块》。

这道题是经典的连通块搜索与**形状归一化（哈希/去重）**相结合的题目。虽然题目背景是俄罗斯方块，但实际上考察的是你处理二维网格图形的能力。

我们先拿出草稿纸，把解题思路一步步拆解出来。

1. 读题关键词：你的“雷达”响了吗？

在读题时，请圈出以下几个决定解题策略的关键信息：

1. “四连通”、“直接或间接连通”：
   • 这明确告诉我们需要进行连通块搜索。也就是经典的 Flood Fill（洪水填充） 算法，用 BFS 或 DFS 均可。
   • 你需要遍历整个网格，找到每一个独立的色块。
2. “平移...重合”：
   • 这是本题的核心难点。如何判断两个形状是否相同？
   • 旋转和翻转题目没提，通常默认不需要考虑（题目只说了“平移”）。
   • 这意味着我们需要找到一种**“标准身份证”**（归一化表示法）来描述一个形状，使得无论它在地图的哪个角落，只要形状一样，“身份证”就一样。
3. “种类数”：
   • 我们需要对找到的所有形状进行去重。
   • 也就是把所有形状扔进一个集合（Set）里，最后看集合的大小。

2. 预备知识点

要解决这道题，你需要掌握：

• 图的遍历：DFS（深度优先搜索）或 BFS（广度优先搜索），用于找连通块。
• 坐标处理：
  • 相对坐标的概念。
  • pair<int, int> 的使用。
• STL 容器：
  • vector：存储一个连通块里的所有点。
  • set：用于存储形状并自动去重。
  • sort：对坐标进行排序，确保比较的唯一性。

3. 启发式教学：草稿纸上的推演

第一步：如何提取一个方块？ 假设地图如下（数字代表颜色）：

. . . .
. 1 1 .  (行2)
. . 1 .  (行3)
. . . .
  (列2,3)

我们可以用 DFS 找到这三个点：$A(2,2), B(2,3), C(3,3)$。 此时我们得到了一个点集：$\{(2,2), (2,3), (3,3)\}$。

第二步：如何让形状“无视位置”？（归一化） 如果有另一个形状在角落里：

. . . .
. . . .
4 4 . .  (行3)
. 4 . .  (行4)
(列1,2)

点集是：$\{(3,1), (3,2), (4,2)\}$。 直接比较坐标，显然不相等。但是它们形状是一样的。

思考：怎么把它们变成一样的？ 方法：找一个基准点（Anchor）！通常选最上、最左的那个点。

• 形状1的基准点：最小行是2，最小列是2 $\to$ 基准 $(2,2)$。
• 形状2的基准点：最小行是3，最小列是1 $\to$ 基准 $(3,1)$。

操作：把所有点的坐标减去基准点的坐标，变成相对坐标。

• 形状1：
  • $(2,2) - (2,2) \to (0,0)$
  • $(2,3) - (2,2) \to (0,1)$
  • $(3,3) - (2,2) \to (1,1)$
  • 结果：$\{(0,0), (0,1), (1,1)\}$
• 形状2：
  • $(3,1) - (3,1) \to (0,0)$
  • $(3,2) - (3,1) \to (0,1)$
  • $(4,2) - (3,1) \to (1,1)$
  • 结果：$\{(0,0), (0,1), (1,1)\}$

惊喜！它们的相对坐标序列完全一样了！这就是它们的“身份证”。

第三步：去重 为了保证比较的唯一性，我们需要对相对坐标进行排序。 比如 $\{(1,1), (0,0)\}$ 和 $\{(0,0), (1,1)\}$ 应该是一样的。排序后都变成 $\{(0,0), (1,1)\}$。 最后，把这个排序后的 vector<pair<int,int>> 扔进 set 里。

4. 核心逻辑梳理

1. 遍历全图：双重循环遍历 $i, j$。
2. 发现新大陆：如果 grid[i][j] 没有被访问过 (vis[i][j] == false)：
   • 启动 BFS/DFS。
   • 记录这个连通块里所有的坐标，存入一个列表 current_shape。
   • 同时记录这个连通块的 min_x 和 min_y。
3. 形状标准化：
   • 遍历 current_shape，把每个点变成 $(x - min\_x, y - min\_y)$。
   • 对 current_shape 进行排序（默认按x再按y排）。
4. 入库：
   • 将处理好的 current_shape 插入 set<vector<pair<int,int>>> shapes。
5. 输出：
   • shapes.size() 就是答案。

现在，请尝试自己写一下代码框架，特别是BFS部分和坐标转换部分。写好了我们再对答案！