你好！作为金牌教练，我非常欣赏你对“最优复杂度”的追求。在 NOI 竞赛中，当数据规模（如 $M, N$）从 $50$ 提升到 $500$ 甚至更大时，使用 std::set<string> 或 std::set<vector> 可能会因为容器内部频繁的内存申请和长字符串/序列的比较开销而导致 TLE（时间超限）。

哈希加速（Hash Acceleration） 的核心思想是将一个复杂的“形状描述”压缩成一个固定的“大整数”。这样，去重时的比较操作就从 $O(L)$（序列长度）降到了 $O(1)$。

一、 预备知识点

1. 字符串哈希（String Hash）： 将一个序列看作一个 $P$ 进制数。
2. 滚动哈希原理： $H = (H \times P + \text{value}) \pmod M$。
3. 单哈希 vs 双哈希： 为了防止哈希碰撞（两个不同形状算出同一个哈希值），在顶级竞赛中通常使用 unsigned long long 自然溢出，或者采用双模数哈希。
4. 序列化闭环： 必须包含“进入”和“回溯”两个动作，才能确保哈希值的唯一性。

二、 启发式引导：在草稿纸上模拟哈希过程

假设我们定义：1:上, 2:下, 3:左, 4:右, 5:回溯。

1. 画图： 画一个“L”型岛屿。
2. 序列化： 你走的路径可能是 [4, 2, 5, 5]（向右，向下，回溯，回溯）。
3. 计算哈希值：
   • 初始 $H = 0$, 基数 $P = 131$。
   • 遇到 4：$H = 0 \times 131 + 4 = 4$
   • 遇到 2：$H = 4 \times 131 + 2 = 526$
   • 遇到 5：$H = 526 \times 131 + 5 = 68911$
   • ...
4. 结论： 最终这个“L”型会被压缩成一个 unsigned long long 类型的数字。将这个数字存入 set<ull>，去重速度极快。

三、 哈希加速标准代码 (NOIP/NOI C++14)

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

using namespace std;

// 使用 unsigned long long 自然溢出，相当于对 2^64 取模
typedef unsigned long long ull;

const int MAXN = 505;
const ull BASE = 131; // 常用哈希基数（质数）
int grid[MAXN][MAXN];
int M, N;

// 记录当前岛屿的哈希值
ull current_hash;

/**
 * DFS 序列化哈希
 * @param r, c 当前坐标
 * @param dir 进入当前格子的方向编号 (1-4)
 */
void dfs(int r, int c, int dir) {
    if (r < 0 || r >= M || c < 0 || c >= N || grid[r][c] == 0) return;

    grid[r][c] = 0; // 沉岛

    // 1. 进入当前节点：更新哈希值
    current_hash = current_hash * BASE + (ull)dir;

    // 递归四个方向
    dfs(r - 1, c, 1); // 上
    dfs(r + 1, c, 2); // 下
    dfs(r, c - 1, 3); // 左
    dfs(r, c + 1, 4); // 右

    // 2. 关键点：回溯。必须记录回溯动作，否则无法区分某些拓扑结构
    // 我们定义 5 为回溯标记
    current_hash = current_hash * BASE + 5;
}

int main() {
    // 1. 读入数据
    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]);
        }
    }

    // 2. 使用 set 存储哈希值进行去重
    set<ull> distinct_shapes;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                current_hash = 0; // 重置哈希
                dfs(i, j, 9);     // 起始方向设为 9 (任意不与1-5冲突的数字)
                distinct_shapes.insert(current_hash);
            }
        }
    }

    // 3. 输出结果
    printf("%zu\n", distinct_shapes.size());

    return 0;
}

四、 复杂度分析思考过程

1. 时间复杂度：

   • 网格遍历： 每个格子只被扫描一次，$O(M \times N)$。
   • 哈希计算： 在 DFS 过程中，哈希值的计算是 $O(1)$ 的乘加运算。
   • 去重开销： 假设岛屿数量为 $K$，set<ull> 的插入复杂度为 $O(\log K)$。由于 ull 的比较是常数级的，这比 set<string> 快得多。
   • 结论： $O(M \times N + K \log K)$。在 $500 \times 500$ 的极限规模下，这是最优的。

2. 空间复杂度：

   • $O(M \times N)$。主要开销是网格存储和递归栈。
   • 哈希值只占用 set<ull> 的空间，相比存储成千上万个字符串，空间消耗极低。

五、 时间复杂度优化建议（教练进阶技巧）

1. 双哈希防御： 虽然 unsigned long long 自然溢出在绝大多数 NOI 题目中能过，但如果出题人恶意构造“哈希冲突”数据，你可以使用双哈希：

   pair<ull, ull> h; 
   h.first = (h.first * BASE1 + dir) % MOD1;
   h.second = (h.second * BASE2 + dir) % MOD2;
   

2. 容器替换： 如果时间依然吃紧，可以使用 std::unordered_set<ull>。它的底层是哈希表，插入复杂度理论上是 $O(1)$。 注意：在 NOI 中，使用 unordered_set 记得加 distinct_shapes.reserve(10000); 预分配空间，防止频繁 rehash。
3. 减少函数压栈： 对于 $500 \times 500$ 规模，虽然哈希版 DFS 很快，但在 Linux 环境下若栈空间有限，建议使用 std::stack 或 std::queue 手动模拟。但注意：BFS 很难直接生成这种带有回溯特征的路径哈希。如果用 BFS，建议使用“相对坐标集合排序后哈希”的方法。

六、 总结读题关键词

• “不同形状” + “大数据范围” $\rightarrow$ 哈希 (Hash)。
• “平移相同” $\rightarrow$ 相对特征 (方向序列或相对坐标)。
• “连通块” $\rightarrow$ DFS/BFS。

金牌教练点评： 哈希是 OI 选手的“降维打击”工具。将几何形状通过 DFS 序列化为数字哈希值，是解决这类匹配问题的终极方案。记住：没有记录回溯的哈希是不完整的。去试一下这个版本，感受一下速度的飞跃！加油！

你好！作为金牌教练，我为你准备了这一题的数据生成器。

由于“不同岛屿的数量”涉及到形状比对，数据生成的质量直接决定了能否卡掉一些错误的哈希算法（例如：不记录回溯路径的序列化、不排序的相对坐标法等）。

数据生成器设计规格

1. 覆盖范围：

   • Test 1-2: 最小边界与全空图。
   • Test 3-4: 单一巨大岛屿与棋盘格（大量微小岛屿）。
   • Test 5: 平移与旋转/镜像区分测试。构造形状相似但平移后无法重合的岛屿（如 L 型与其旋转版本）。
   • Test 6-7: 随机稀疏与随机稠密。
   • Test 8: 路径压力测试。构造极长的蛇形路径，测试 DFS 序列化的健壮性。
   • Test 9: 复杂克隆测试。在不同位置生成两个结构极其复杂的完全相同的岛屿，检测哈希/去重能力。
   • Test 10: 最大规模综合测试点 ($100 \times 100$)。

2. 安全性：

   • 标程使用 BFS + 相对坐标集合排序 的方式生成 .out，这种方法比路径字符串更稳健且绝不爆栈。
   • 文件大小控制：10 组数据总大小约 500KB。

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

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

using namespace std;

// --- 内部标程：使用 BFS + 坐标归一化，确保生成结果绝对正确且不爆栈 ---
int solve(int M, int N, vector<vector<int>> grid) {
    if (M <= 0 || N <= 0) return 0;
    set<vector<pair<int, int>>> shapes;
    vector<vector<bool>> vis(M, vector<bool>(N, false));
    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 (grid[i][j] == 1 && !vis[i][j]) {
                vector<pair<int, int>> island;
                queue<pair<int, int>> q;
                
                q.push({i, j});
                vis[i][j] = true;
                int min_r = i, min_c = j;

                while (!q.empty()) {
                    pair<int, int> cur = q.front(); q.pop();
                    island.push_back(cur);
                    for (int k = 0; k < 4; k++) {
                        int nr = cur.first + dx[k], nc = cur.second + dy[k];
                        if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] == 1 && !vis[nr][nc]) {
                            vis[nr][nc] = true;
                            q.push({nr, nc});
                        }
                    }
                }
                // 归一化：所有坐标减去该岛屿左上角(第一个发现的点)坐标
                for (auto &p : island) {
                    p.first -= i;
                    p.second -= j;
                }
                sort(island.begin(), island.end());
                shapes.insert(island);
            }
        }
    }
    return (int)shapes.size();
}

// --- 数据生成逻辑 ---
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 = 50, N = 50;
    if (id <= 2) { M = id; N = id; }
    if (id == 10) { M = 100; N = 100; }

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

    if (id == 1) grid[0][0] = 1;
    else if (id == 2) grid[0][0] = 0;
    else if (id == 3) { // 一个巨大的岛
        for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = 1;
    }
    else if (id == 4) { // 棋盘格
        for(int i=0; i<M; i++) for(int j=0; j<N; j++) grid[i][j] = (i+j)%2;
    }
    else if (id == 5) { // 旋转与镜像区分 (L型)
        // 形状 1
        grid[2][2] = grid[3][2] = grid[3][3] = 1;
        // 形状 2 (旋转版，在本题中应视为不同)
        grid[2][10] = grid[2][11] = grid[3][10] = 1;
        // 形状 3 (形状1的克隆，应去重)
        grid[10][10] = grid[11][10] = grid[11][11] = 1;
    }
    else if (id == 8) { // 蛇形路径压力点
        for(int i=0; i<M; i++) {
            if (i % 4 == 0) for(int j=0; j<N-2; j++) grid[i][j] = 1;
            else if (i % 4 == 1) grid[i][N-3] = 1;
            else if (i % 4 == 2) for(int j=2; j<N; j++) grid[i][j] = 1;
            else if (i % 4 == 3) grid[i][2] = 1;
        }
    }
    else if (id == 9) { // 复杂形状克隆测试
        for(int k=0; k<2; k++) { // 在两个地方生成一模一样的复杂随机块
            int offset_r = k * 20 + 2, offset_c = 5;
            srand(42); // 固定种子保证形状一样
            for(int i=0; i<10; i++) for(int j=0; j<10; j++) 
                if(rand()%2) grid[offset_r + i][offset_c + j] = 1;
        }
    }
    else { // 随机
        srand(time(0) + id);
        int p = (id == 6) ? 10 : 35;
        for(int i=0; i<M; i++) for(int j=0; j<N; j++) if(rand()%100 < p) grid[i][j] = 1;
    }

    // 写入文件
    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";
    }

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

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

教练对数据点的深度分析：

1. Test 5 (旋转/镜像测试)： 很多选手在做这一题时会错误地认为“旋转后相同也算同一种”。这组数据故意放置了 $L$ 型和它旋转 $90^\circ$ 后的形状。

   • 如果输出 1，说明选手误解了“平移重合”的定义。
   • 如果输出 2，说明去重逻辑正确。

2. Test 8 (蛇形路径)： 构造了长达数千个格子的单连通块。

   • DFS 序列化选手：如果不带回溯标记（Backtrack flag），或者递归深度没处理好，此处会报错或结果错误。
   • 相对坐标选手：需要处理大数组的排序性能。

3. Test 9 (哈希碰撞测试)： 构造了两个完全一致的 $10 \times 10$ 复杂随机岛屿。如果选手的哈希函数不够严谨（例如只计算面积或周长），这里会因为哈希冲突导致输出结果偏小。

4. OJ 评测建议：

   • 时间限制 (TL): 1.0s。$100 \times 100$ 规模下，$O(MN \log MN)$ 的算法应该在 50ms 内完成。
   • 内存限制 (ML): 256MB。主要是为了给 std::set 和 std::string 留足空间。

教练寄语： 数据生成器的意义在于寻找算法的边界。通过这 10 个测试点，你可以确保学生不仅学会了 DFS，更学会了如何严谨地提取一个几何形状的“指纹”。加油！

你好！我是教练。这道题是岛屿系列中对“数据抽象”要求最高的一道。判定两个形状是否相同，本质上是寻找一种**“唯一标识（Signature）”**。

在 NOI 竞赛中，我们通常有两条演进路线：从坐标集合化到路径序列化，再到哈希加速。

版本一：坐标归一化 + 容器去重（最稳健版）

思路： 当我们找到一个岛屿时，记录下它所有格子的相对坐标。例如，如果岛屿起点是 $(r_0, c_0)$，那么点 $(r, c)$ 的相对位置就是 $(r-r_0, c-c_0)$。我们将这些相对坐标存入 vector 并排序，作为 set 的键。

时间复杂度： $O(MN \cdot S \log S)$，其中 $S$ 是岛屿大小（排序开销）。 空间复杂度： $O(MN)$，用于存储所有岛屿的坐标。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int MAXN = 55;
int grid[MAXN][MAXN];
int M, N;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 存储当前正在搜索的岛屿相对坐标
vector<pair<int, int>> current_island;

void dfs(int r, int c, int r0, int c0) {
    grid[r][c] = 0; // 沉岛
    // 关键点：记录相对于起始点 (r0, c0) 的偏移量
    current_island.push_back({r - r0, c - c0});

    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] == 1) {
            dfs(nr, nc, r0, c0);
        }
    }
}

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]);

    // 使用 set 对 vector 进行去重
    set<vector<pair<int, int>>> shapes;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                current_island.clear();
                // 以当前点 (i, j) 作为基准点
                dfs(i, j, i, j);
                // 易错点：DFS 的顺序虽然固定，但为了保险，排序能确保形状唯一
                sort(current_island.begin(), current_island.end());
                shapes.insert(current_island);
            }
        }
    }

    printf("%zu\n", shapes.size());
    return 0;
}

版本二：路径序列化（竞赛常用版）

思路： 不需要记录坐标，而是记录 DFS 的**“探险路径”**。当我们向上下左右走时，记录 1, 2, 3, 4，当回溯时记录 0。

为什么必须记录回溯？ 如果不记录回溯，路径 右->下 和 右(回退)下 可能会产生同样的序列，但形状不同。

复杂度分析： 字符串拼接比 vector 排序更快。时间复杂度 $O(MN \log K)$。

#include <iostream>
#include <string>
#include <set>
#include <vector>

using namespace std;

int M, N;
int grid[55][55];
string path;

// 1:上, 2:下, 3:左, 4:右, 0:回溯
void dfs(int r, int c, int dir) {
    if (r < 0 || r >= M || c < 0 || c >= N || grid[r][c] == 0) return;
    
    grid[r][c] = 0;
    path += to_string(dir); // 记录进入的方向

    dfs(r - 1, c, 1);
    dfs(r + 1, c, 2);
    dfs(r, c - 1, 3);
    dfs(r, c + 1, 4);

    path += "0"; // 关键点：记录回溯，否则无法区分某些长条形岛屿
}

int main() {
    cin >> M >> N;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++) cin >> grid[i][j];

    set<string> distinct_islands;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                path = "";
                dfs(i, j, 6); // 起始方向随便给个不冲突的编号
                distinct_islands.insert(path);
            }
        }
    }
    cout << distinct_islands.size() << endl;
    return 0;
}

版本三：哈希加速（最优复杂度方案）

思路： 当 $M, N$ 很大（如 500）时，set<string> 插入时长字符串的比对会变成瓶颈。我们可以将路径字符串转化为 单哈希或双哈希值（unsigned long long），将 set 的比较复杂度从 $O(L)$ 降到 $O(1)$。

时间复杂度： $O(MN)$。

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

1. 时间复杂度思考：

• 本题的核心开销不在搜索，而在去重。
• set<vector> 的效率取决于 vector 的大小和 set 的深度。对于 $50 \times 50$，这是安全的；对于更高量级，必须上哈希。

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

• 坐标表示： 在版本一中，可以将 pair<int, int> 压缩成一个 int：rel_r * 100 + rel_c，这能加快 sort 和 set 的比对速度。
• 容器选择： 在 C++11 以后，如果哈希函数写得好，unordered_set 理论上比 set 快，但在 OI 竞赛中，为了防止被构造数据（Anti-hash）卡掉，通常首选稳定的 set。

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

• 字符串池： 路径字符串可以使用全局变量 string 并通过 clear() 复用，避免频繁申请内存。

读题关键词总结

• “不同” (Distinct)：预示着需要使用 set 或哈希表进行去重。
• “平移” (Translation)：暗示了相对特征是关键。起始点归零化是处理平移不变性的通用技巧。
• “形状” (Shape)：形状的本质是拓扑结构。在搜索中，DFS 序列（带回溯标记）是描述拓扑结构的唯一标识。

金牌教练点评： 这道题不仅考察 DFS，更是一道**“特征建模”**的题。在草稿纸上模拟时，如果你能画出两个不同的 L 型并发现如果不记“回溯”它们的路径序列是一样的，你就已经掌握了这道题的精髓。加油！