你好！我是教练。在掌握了岛屿的“数量”、“面积”和“包含关系”后，我们迎来了岛屿系列中最具算法深度的一个课题：“不同岛屿的数量”。

这道题在 NOI 竞赛中属于**“搜索 + 哈希/序列化”的综合题型。它不仅要求你找到连通块，还要求你具备“特征提取”**的能力，即：如何判断两个形状复杂的岛屿在平移后是完全重合的？

一、 题目描述：不同岛屿的数量 (Number of Distinct Islands)

题目背景： 在地图版权识别中，我们需要统计地图中不同形状的岛屿数量。如果一个岛屿可以通过平移（不能旋转或镜像）与另一个岛屿重合，则认为它们是相同的。

任务描述： 给你一个 $M \times N$ 的二进制矩阵 grid，其中 1 表示陆地，0 表示水域。 一个岛屿是由水平或垂直方向相邻的 1 形成的连通块。 请计算并返回矩阵中不同岛屿的数量。

输入格式： 第一行包含两个整数 $M$ 和 $N$ ($1 \le M, N \le 50$)。 接下来的 $M$ 行，每行包含 $N$ 个用空格分隔的整数（0 或 1）。

输出格式： 输出一个整数，表示不同形状岛屿的数量。

样例 1 输入：

4 5
1 1 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1

样例 1 输出：

1

(解析：左上角和右下角的岛屿形状相同，平移后重合，计为 1 种)

样例 2 输入：

5 4
1 1 0 0
1 0 0 0
0 0 0 0
1 1 0 0
0 1 0 0

样例 2 输出：

2

(解析：上方的岛屿是 L 型，下方的岛屿也是 L 型但朝向不同。注意：本题只允许平移，不允许旋转，所以它们是 2 种不同的岛屿)

二、 预备知识点

1. 连通块遍历 (DFS/BFS)： 基础搜索框架。
2. 坐标标准化 (Normalization)： 将绝对坐标转化为相对于岛屿起点的相对坐标。
3. 序列化 (Serialization)： 将一个形状转化为唯一的字符串或数值序列。
4. 去重容器 (std::set / std::unordered_set)： 存储岛屿的特征。

三-1. 启发式引导：草稿纸上的形状比对

请拿出草稿纸，跟我一起思考：如何描述一个岛屿的“长相”？

方法 A：相对坐标法

1. 记录岛屿中所有格子的坐标：$(r_1, c_1), (r_2, c_2), \dots$
2. 选取岛屿的第一个点（搜索起点）作为基准点 $(r_0, c_0)$。
3. 将所有坐标减去基准点，得到相对坐标序列：$(r_1-r_0, c_1-c_0), \dots$
4. 注意： 为了确保唯一性，相对坐标序列必须按固定顺序（如从小到大）排列。

方法 B：路径方向法（教练推荐：实现更简洁）

1. 在 DFS 过程中，记录你走的每一个动作。
2. 例如：1 (上), 2 (下), 3 (左), 4 (右)。
3. 关键陷阱： 必须记录“回溯”动作。如果没有回溯标记，某些不同的形状可能会生成相同的路径字符串。
   • 例如：记录 开始->右->下->回溯->回溯->结束。

三-2. 时间与空间复杂度分析思考

• 时间复杂度： $O(M \times N \times \log(K))$。$M \times N$ 是遍历网格的时间，$K$ 是岛屿数量，$\log$ 来自于将形状存入 std::set。
• 空间复杂度： $O(M \times N)$。用于存储 vis 数组以及所有岛屿的特征序列。

四、 算法流程图 (Mermaid 风格)

我们采用“路径方向序列化”法来绘制流程：

graph TD
    Start("开始") --> InitSet("创建 set 存储不同形状的字符串")
    InitSet --> LoopGrid("遍历网格每个点 i, j")
    LoopGrid --> IsNewLand{"是未访问的陆地吗?"}
    
    IsNewLand -- "是" --> StartDFS("以此为起点开启 DFS")
    StartDFS --> RecordPath("记录当前方向编号到 path 字符串")
    RecordPath --> MoveNext("递归尝试四个方向")
    MoveNext --> Backtrack("递归返回时记录回溯标记到 path")
    Backtrack --> SaveShape("将完整 path 存入 set")
    
    SaveShape --> LoopGridNext("检查下一个格子")
    IsNewLand -- "否" --> LoopGridNext
    
    LoopGridNext --> EndGrid{"全图扫描结束?"}
    EndGrid -- "是" --> Output("输出 set 的大小")

五、 读题理解关键词

在 NOI 竞赛中，遇到此类题目的识别信号：

1. “不同” (Distinct / Unique)：
   • 这是最核心的信号，意味着需要去重。
   • 策略： 必须找到一种方法给每个连通块生成一个“身份证号”。
2. “平移” (Translation)：
   • 意味着特征提取必须是相对位置敏感但绝对位置无关的。
   • 对比： 如果题目说“旋转或镜像后相同”，那难度会大幅提升（需要引入坐标变换的归一化）。
3. 数据范围 (50)：
   • $50 \times 50$ 的规模非常小。这意味着你可以放心地使用 std::string 拼接，甚至可以使用 std::set<vector<pair<int, int>>> 这种比较重的容器。

六、 时间复杂度优化建议

1. 路径压缩优化： 在记录路径时，可以用字符 'u','d','l','r','b' (b代表backtrack) 拼接。
2. 哈希优化： 如果 $M, N$ 达到 $500$ 级，std::set<string> 的比较操作会变慢。此时建议对生成的字符串进行 String Hash (字符串哈希) 处理，将字符串转为一个 unsigned long long 的数值。
3. 排序技巧： 如果使用相对坐标法，确保在存入 set 前对坐标列表进行排序。

教练点评： “不同岛屿的数量”是搜索题中的一个分水岭。它考察了你如何将“空间形状”这种感性信息，转化为“数据序列”这种理性信息。掌握了序列化思维，你就掌握了处理复杂几何匹配问题的万能钥匙！加油！