LeetCode 694. 不同岛屿的数量
目录
题目描述
题意分析
网格里
1是陆地、0是水，四连通的陆地组成一个岛屿。题目不是问有几个岛，而是问有几种互不相同的形状。「相同」的定义写得很克制：两个岛如果能通过平移互相重合，就算同一种形状。注意题面只允许平移，不允许旋转，也不允许翻转。这是本题最重要的约束信号——它意味着形状的判定要保留方向信息，一个「向右伸出去的钩子」和一个「向下伸出去的钩子」是两种形状。
由此可以推出问题的本质：要为每个岛屿造一个平移不变的指纹，让形状相同的岛拿到相同的指纹、形状不同的岛拿到不同的指纹，然后数一数有几种指纹。
边界上要考虑：网格里没有任何陆地（答案是
0）、整张网格全是陆地（只有一种形状）、多个只有一格的岛（都算同一种形状）、以及岛屿贴着网格四边导致某些方向越界。
解法：DFS 路径签名
核心思路
最朴素的做法是把每个岛屿的格子坐标集合存下来，再两两比较是否能通过平移重合。比较两个岛需要先做归一化（比如都减去各自左上角坐标）再逐点对照，岛屿多的时候是 $O(k^2)$ 次集合比较，写起来也繁琐。
瓶颈在于「先收集再两两比对」这条路径。观察一下：既然要判等，不如直接为每个岛算出一个可以哈希的字符串指纹，把两两比对换成往集合里丢。
那么指纹怎么造才既平移不变、又能区分形状？关键观察是：从岛屿的某个固定起点出发、按固定顺序做 DFS，走过的方向序列就完全刻画了岛屿的结构，并且和绝对坐标无关。只要两个岛形状相同，DFS 从各自的起点出发就会走出一模一样的方向序列。
起点必须选得一致。外层是按行优先扫描网格的，第一个碰到的陆地格必然是这个岛里「行号最小、同行中列号最小」的那一格，这个位置只由形状决定、不受平移影响，天然满足要求。
只记录进入方向还不够。方向序列相同但分叉位置不同的两个岛会撞签名，因为字符串没法表达「什么时候回到上一层」。补救办法是每次递归返回时追加一个回退标记
'B'，这样字符串就变成了对 DFS 树的完整括号化编码，树形结构被唯一确定。显式的不变量是：对任意一个岛屿，从它的行优先最小格出发、按「上、下、左、右」这个固定顺序递归、并在每层返回时追加
'B'，得到的字符串与岛屿在网格中的位置无关，且与岛屿形状一一对应。把所有岛的签名丢进哈希集合，集合大小就是答案。
解题步骤
- 准备一个字符串集合
shapes用来去重。选集合而不是计数器，是因为要数的是「形状种类」而不是「岛屿个数」。- 按行优先双层循环扫描整个网格，遇到
grid[row][col] == 1就说明发现了一个尚未处理的新岛屿，且当前格就是这个岛的行优先最小格。- 为这个岛新建一个空的路径缓冲，调用 DFS，起始方向字符用
'S'。每个岛必须用独立的缓冲，共用一个会让后面的岛签名带上前面岛的尾巴。- DFS 里先做统一的边界与水域判断：行列越界或者当前格是
0就直接返回，且不追加任何字符。把四种越界情况合并成一个判断，比在四个递归调用前各写一遍可靠得多。- 通过判断后立刻把
grid[row][col]置为0。这一步必须在递归之前做，否则相邻两格会互相递归成死循环。置0同时充当了访问标记，省掉一个visited数组。- 追加当前的方向字符，然后按「上、下、左、右」的固定顺序递归四个邻居，分别传入
'U'、'D'、'L'、'R'。顺序必须在所有岛之间保持一致，否则同一形状会产生不同签名。- 四个方向全部递归完后追加一个
'B'。这个回退标记是区分分叉结构的关键，缺了它不同形状会撞签名。- DFS 返回后把路径字符串加进集合。全部扫描结束，返回集合的大小。
以
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]走一遍：这是两个 2×2 的方块岛，一个在左上角，一个在右下角，形状显然相同，期望答案是1。扫描到
(0, 0)时启动第一次 DFS。当前格置0，路径"S"。向上越界返回；向下进入(1, 0)，置0，路径"SD"；(1, 0)向上回到(0, 0)，此时它已是0，返回；向下是(2, 0)为水，返回；向左越界；向右进入(1, 1)，置0，路径"SDR"；(1, 1)向上进入(0, 1)，置0，路径"SDRU"；(0, 1)的四个方向要么越界要么是水，追加'B'得"SDRUB"；回到(1, 1)，其余三个方向都无效，追加'B'得"SDRUBB"；回到(1, 0)，追加'B'得"SDRUBBB"；回到(0, 0)，它的左越界、右邻(0, 1)已变成0，追加'B'得"SDRUBBBB"。集合里加入"SDRUBBBB"。继续扫描，第一行剩下的格子和第二行的格子都已经是
0，一路跳过，直到(2, 3)又是1，启动第二次 DFS。完全同构的过程走一遍：(2,3)置0得"S"，下到(3,3)得"SD"，右到(3,4)得"SDR"，上到(2,4)得"SDRU"，然后四次返回依次追加'B'，最终同样是"SDRUBBBB"。这个字符串在集合里已经存在，插入无效果。扫描结束时集合只有一个元素，返回
1。
代码实现
class Solution {
public int numDistinctIslands(int[][] grid) {
Set<String> shapes = new HashSet<>();
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == 1) {
StringBuilder path = new StringBuilder();
dfs(grid, row, col, 'S', path);
shapes.add(path.toString());
}
}
}
return shapes.size();
}
private void dfs(int[][] grid, int row, int col, char dir, StringBuilder path) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {
return;
}
grid[row][col] = 0;
path.append(dir);
dfs(grid, row - 1, col, 'U', path);
dfs(grid, row + 1, col, 'D', path);
dfs(grid, row, col - 1, 'L', path);
dfs(grid, row, col + 1, 'R', path);
path.append('B');
}
}
func numDistinctIslands(grid [][]int) int {
shapes := make(map[string]bool)
var dfs func(int, int, byte, *[]byte)
dfs = func(row int, col int, dir byte, path *[]byte) {
if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] == 0 {
return
}
grid[row][col] = 0
*path = append(*path, dir)
dfs(row-1, col, 'U', path)
dfs(row+1, col, 'D', path)
dfs(row, col-1, 'L', path)
dfs(row, col+1, 'R', path)
*path = append(*path, 'B')
}
for row := 0; row < len(grid); row++ {
for col := 0; col < len(grid[0]); col++ {
if grid[row][col] == 1 {
path := []byte{}
dfs(row, col, 'S', &path)
shapes[string(path)] = true
}
}
}
return len(shapes)
}
复杂度分析
- 时间复杂度：$O(mn)$，
m和n是网格的行数与列数。外层扫描访问每格一次，DFS 中每个陆地格进入后立刻被置0，因此最多被展开一次；每格向四个方向各发起一次调用，总调用数是 $O(mn)$。签名字符串的总长度也是 $O(mn)$ 量级，哈希与比较的开销同阶。- 空间复杂度：$O(mn)$，最坏情况下整张网格是一个蛇形岛屿，递归栈深度和单条签名长度都能达到 $O(mn)$；形状集合里所有签名的总长度同样受这个上界约束。原网格被复用作访问标记，没有额外的
visited数组。
关键点总结
- 「判断两个结构是否等价」的问题，优先想能不能造一个规范形式（canonical form），把等价判定转成字符串相等。造出规范形式后，两两比对的 $O(k^2)$ 立刻塌缩成一次哈希插入。
- 规范形式的两个必要条件是「起点唯一」和「遍历顺序固定」。这题的起点由行优先扫描天然给出，顺序则要靠自己约定并全程不变——两者缺一，同形状就会产生不同签名。
- 括号化编码（进入写方向、返回写
'B'）是把树结构无损压成字符串的通用技巧，序列化二叉树、比较子树是否相同等题目用的都是同一套。只记进入不记返回，等于丢掉了层级信息。- 复用输入网格当访问标记，前提是允许修改输入且不需要二次遍历。面试时值得主动说一句「这里我把
1改成了0，如果面试官要求不修改输入，我会加一个visited数组」，显示你知道这是个取舍而不是随手写的。- 面试视角：最高频的追问是「如果允许旋转和翻转还算同一种形状呢」（第 711 题）。答案是为每个岛生成
8种变换（4个旋转乘镜像）下的相对坐标集合，取字典序最小的那个当规范形式。能指出「本题只允许平移，所以方向序列就够用」，说明你抓住了约束与解法的对应关系。- 面试视角：另一个常见追问是「不用字符串还能怎么做指纹」。可以把每个格子相对起点的偏移
(dr, dc)收集起来排序后拼成串，这种写法不依赖遍历顺序，也不需要回退标记，正确性更容易讲清楚，代价是多一次排序。
易错点总结
- 错误写法：只把进入方向写进签名，省略递归返回时追加的
'B'。用例 两个岛屿的方向序列相同但分叉深度不同（比如同一条链上，一个岛在第二格向旁边伸出一格、另一个岛在第三格伸出一格）→ 两串字符完全一致，不同形状被合并成一种，答案偏小。- 错误写法：DFS 的四个方向顺序在不同岛屿之间不一致，例如按邻居坐标动态排序后再递归。用例 两个位置不同但形状完全相同的岛 → 遍历顺序不同导致签名不同，同一形状被算成两种，答案偏大。
- 错误写法：DFS 里不把访问过的陆地置
0。用例[[1, 1]]→(0,0)向右递归到(0,1)，(0,1)又向左递归回(0,0)，两格互相调用直到栈溢出。- 错误写法：把「当前格置
0」放在四个方向递归之后。用例[[1, 1]]→ 置0永远轮不到执行，效果和完全不标记一样，同样栈溢出。- 错误写法：用格子的绝对坐标集合当签名。用例
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]→ 两个岛的坐标集合分别是{(0,0),(0,1),(1,0),(1,1)}和{(2,3),(2,4),(3,3),(3,4)}，被判成两种形状，返回2而不是1。- 错误写法：所有岛屿共用同一个路径缓冲，不在每次外层调用前清空。用例
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]→ 第二个岛的签名变成第一个岛的签名再接上自己的部分，与第一个岛不同，返回2而不是1。- 错误写法：越界检查在四个递归调用点分别手写，漏掉其中一侧。用例
[[1]]→ 向上递归时row - 1为-1没被拦住，访问grid[-1][0]直接越界崩溃。- 错误写法：把外层遇到
1的次数直接当答案，忘了往集合里塞签名去重。用例[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]→ 数出来的是岛屿总数2，而题目问的是形状种类数1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 连通块计数的最简形态，不需要为岛屿构造任何指纹 |
| 695. 岛屿的最大面积 | 中等 | DFS 带返回值向上累加格子数，练的是聚合而非结构描述 |
| 463. 岛屿的周长 | 简单 | 逐格统计暴露在外的边，完全不依赖连通性遍历 |
| 130. 被围绕的区域 | 中等 | 从边界反向出发染色，把「不满足条件」的部分先标出来 |
| 1020. 飞地的数量 | 中等 | 先消掉贴边的连通块，再统计剩余陆地格数 |
| 1254. 统计封闭岛屿的数目 | 中等 | 水陆角色互换，判定条件是整块岛是否完全不接触边界 |
| 面试题 16.19. 水域大小 | 中等 | 连通性定义为八连通，方向数组要从 4 个扩到 8 个 |
| LCR 105. 岛屿的最大面积 | 中等 | 同 695 的另一入口，适合用来对照 BFS 与 DFS 两种遍历骨架 |