LeetCode 694. 不同岛屿的数量

Categories:

题目描述
思路分析
1. 解法一：路径编码 + DFS（推荐）
相似题目

题目描述

✅ 694. 不同岛屿的数量

思路分析

解法一：路径编码 + DFS（推荐）

核心思路：

对每个岛屿做 DFS，并记录路径编码（方向 + 回退）。

相同形状的岛屿会得到相同的编码。

用集合去重编码，集合大小即不同岛屿数量。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示网格行列数。

空间复杂度：O(mn)，递归栈与编码集合。

import java.util.HashSet;
import java.util.Set;

class Solution {
    private int m;
    private int n;

    public int numDistinctIslands(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Set<String> shapes = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder path = new StringBuilder();
                    dfs(grid, i, j, path, 'S');
                    shapes.add(path.toString());
                }
            }
        }
        return shapes.size();
    }

    private void dfs(int[][] grid, int x, int y, StringBuilder path, char dir) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
            return;
        }
        grid[x][y] = 0;
        path.append(dir);

        dfs(grid, x + 1, y, path, 'D');
        dfs(grid, x - 1, y, path, 'U');
        dfs(grid, x, y + 1, path, 'R');
        dfs(grid, x, y - 1, path, 'L');

        path.append('B');
    }
}

func numDistinctIslands(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	shapes := make(map[string]bool)

	var dfs func(x, y int, dir byte, path *[]byte)
	dfs = func(x, y int, dir byte, path *[]byte) {
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 {
			return
		}
		grid[x][y] = 0
		*path = append(*path, dir)

		dfs(x+1, y, 'D', path)
		dfs(x-1, y, 'U', path)
		dfs(x, y+1, 'R', path)
		dfs(x, y-1, 'L', path)

		*path = append(*path, 'B')
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				path := make([]byte, 0)
				dfs(i, j, 'S', &path)
				shapes[string(path)] = true
			}
		}
	}

	return len(shapes)
}

相似题目

题目	难度	考察点
694. 不同岛屿的数量	中等	DFS
200. 岛屿数量	中等	DFS
695. 岛屿的最大面积	中等	DFS
1020. 飞地的数量	中等	DFS
1254. 统计封闭岛屿的数目	中等	DFS
130. 被围绕的区域	中等	DFS

本文作者: HGNULB

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