Leetcode 694 Solution

This article provides solution to leetcode question 694 (number-of-distinct-islands)

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

Solution

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(i, j, x, y, a):
            nonlocal grid
            nonlocal m
            nonlocal n

            grid[i][j] = 2
            a.append("{},{}".format(x, y))

            directions = [
                (1, 0),
                (-1, 0),
                (0, 1),
                (0, -1),
            ]

            for di, dj in directions:
                neigh_i = i + di
                neigh_j = j + dj

                if not (0 <= neigh_i < m and 0 <= neigh_j < n):
                    continue

                if grid[neigh_i][neigh_j] == 1:
                    dfs(neigh_i, neigh_j, x + di, y + dj, a)

        s = set()
        for i in range(m):
            for j in range(n):
                a = []
                if grid[i][j] == 1:
                    dfs(i, j, 0, 0, a)
                    s.add(";".join(a))

        return len(s)