Clean python 97% BFS 120ms


  • 0
    W

    BFS

    class Solution(object):
        def numDistinctIslands(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            if not grid or not grid[0]: return 0
            m,n=len(grid),len(grid[0])
    
            # augment matrix to void length check
            grid.append([0]*n)
            for row in grid: row.append(0)
    
            # BFS
            def bfs(i0,j0):
                grid[i0][j0]=-1
                q=[(i0,j0)]
                for i,j in q:
                    for I,J in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
                        if grid[I][J]==1:
                            grid[I][J]=-1
                            q.append((I,J))
                # generate relative position and covert to tuple
                res.add(tuple((x-i0,y-j0) for x,y in q))
    
            res=set()
            for i in range(m):
                for j in range(n):
                    if grid[i][j]==1:
                        bfs(i,j)
    
            return len(res)
    

Log in to reply
 

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