LeetCode 694. 不同岛屿的数量

2022-07-18 HGNULB 约 5 分钟

文章信息 9 个分类 8 个标签

分类

LeetCode CodeTop 中等未解决会员题 5-10 字节华为微软

题目描述

✅ 694. 不同岛屿的数量

题意分析

网格中的 1 是陆地，沿上下左右相连的陆地构成一个岛屿。统计的是不同形状数：两块岛屿只有平移后能完全重合才算相同，不允许通过旋转或镜像使它们重合。代码会把访问过的陆地改为 0，原地完成访问标记。

解法：DFS 路径签名

核心思路

[!blue]

要用集合去重，先把每块岛屿转成与绝对位置无关、又能还原形状的字符串。按行优先扫描时，每块岛屿的起点都是其最上方那一行中最靠左的陆地；平移不会改变这个相对起点。

从起点按固定的上、下、左、右顺序 DFS。首次进入陆地时追加进入方向，起点记为 S，其余记为 U、D、L、R；该格子的四个方向都处理完后，再追加返回标记 B。越界、水域和已访问格子直接返回，不写入签名。

方向说明“走到了哪里”，返回标记说明“何时退回上一层”。若只有进入方向，就无法区分接下来的一步是从当前格子继续走，还是先回到父节点后走向另一个分支。保留 B 后，可以从起点按字符串恢复 DFS 的进退过程，也就能恢复所有陆地相对起点的坐标，因此相同签名必然对应相同形状。

反过来，平移相同的岛屿具有相同的起点规则和邻接关系，固定方向顺序会产生相同的完整签名。把每次遍历得到的签名放入集合，集合大小就是不同形状数；原地置零保证同一格只被访问一次，同一岛屿只生成一次签名。

解题步骤

按行、列顺序扫描，遇到仍为 1 的格子，为它建立空签名并从 S 开始 DFS。

首次进入有效陆地时先置零，再记录进入方向，避免邻接格子再次访问它。

按上、下、左、右顺序递归，处理完后追加 B；这个标记属于最终编码，不能像普通回溯路径那样删除。

将这块岛屿的完整签名加入集合，继续扫描其他岛屿，最后返回集合大小。全是水时集合为空，单个陆地的签名也能正常记录。

代码实现

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$ 为网格行列数。每个陆地格子只遍历一次并生成两个标记，所有签名的构造与哈希总长度均为 $O(mn)$。

空间复杂度：$O(mn)$，用于签名集合、当前岛屿的签名和递归栈；最坏情况下整张网格属于一个岛屿。

关键点总结

[!green]

起点规则和方向顺序必须一致。

回退信息保留树状遍历结构。

原地置零会修改输入网格。

易错点总结

[!yellow]

只记录方向不记录返回，会混淆不同分支形状。

每次任意挑起点，平移相同的岛屿可能得到不同签名。

把旋转或镜像也归并，改变了本题等价条件。

相似题目

题目	难度	关联与区别
200. 岛屿数量	中等	原题只统计岛屿个数，本题还要把每块形状编码后去重，平移后的相同形状算同类。
711. 不同岛屿的数量 II	困难	原题进一步把旋转和镜像后的形状也视为相同，需要对多种变换取规范表示。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/20132090

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！