Python Solution


  • 0
    G
    class Solution:
        def numDistinctIslands(self, grid):
            paths = list()
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    if 1 == grid[i][j]:
                        path = list()
                        self.traversalIslands(grid, i, j, path)
                        paths.append(list(sorted(path)))
    
            return self.count(paths)
    
        def traversalIslands(self, grid, i, j, path):
            if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and 1 == grid[i][j]:
                grid[i][j] = 0
                path.append([i, j])
                self.traversalIslands(grid, i + 1, j, path)
                self.traversalIslands(grid, i - 1, j, path)
                self.traversalIslands(grid, i, j + 1, path)
                self.traversalIslands(grid, i, j - 1, path)
    
        def count(self, paths):
            # transfer matrix
            for i in range(len(paths)):
                if 0 != paths[i][0][0]:
                    for j in range(1, len(paths[i])):
                        paths[i][j][0] -= paths[i][0][0]
                paths[i][0][0] = 0
                if 0 != paths[i][0][1]:
                    for j in range(1, len(paths[i])):
                        paths[i][j][1] -= paths[i][0][1]
                paths[i][0][1] = 0
    
            return len(self.uniq(paths))
    
        def uniq(self, paths):
            unique_paths = list()
            for path in paths:
                find = False
                for p in unique_paths:
                    if p == path:
                        find = True
                if not find:
                    unique_paths.append(path)
    
            return unique_paths
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.