694. 不同岛屿的数量

Difficulty

Medium

Tags

DFS

URL

https://leetcode-cn.com/problems/number-of-distinct-islands/

Star

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

示例 1：

给定上图，返回结果 1 。

示例 2：

给定上图，返回结果 3。

注意：


11
1

和


 1
11

是不同的岛屿，因为我们不考虑旋转、翻转操作。

法 1 DFS

思路

关键在于判断不同岛屿，也就是序列化岛屿形状

一边dfs遍历“1”,一边纪录形状。注意，在离开每个1 的时候，需要添加一个标记“e”

题解


class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        island = set()
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == 1:
                    path = []
                    self.dfs(raw=i, col=j, 
                                grid=grid, path=path, prev="s")
                    island.add("".join(path))
        
        return len(island)


    def dfs(self, raw, col, grid, path, prev):
        # print(path)
        if raw < 0 or raw >= len(grid) or col < 0 or col >= len(grid[0]):
            return
        if grid[raw][col] == 0:
            return

        grid[raw][col] = 0
        path.append(prev)

        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for i, d in enumerate(dirs):
            self.dfs(raw+d[0], col+d[1], grid, path, str(i))
        path.append("e")