749 / 759 test cases passed , Help needed!!


  • 0
    W

    My basic idea is to use BFS+set in python to store the path the BFS explore, but now it can only passes 749/759, any advices will be welcomed

    from collections import deque
    class Solution(object):
        def dfs(self,grid,path,queue,myset):
            while len(queue)!=0:
                level=len(queue)
                while level!=0:
                    cur=queue.popleft()
                    level-=1
                    x=cur[0]
                    y=cur[1]
                    step=cur[2]
                    path.append(step)
                    #try left,up,right,down
                    if y-1>=0 and grid[x][y-1]==1:
                        grid[x][y-1]=0
                        queue.append((x,y-1,'L'))
                    if x-1>=0 and grid[x-1][y]==1:
                        grid[x-1][y]=0
                        queue.append((x-1,y,'U'))
                    if y+1<len(grid[0]) and grid[x][y+1]==1:
                        grid[x][y+1]=0
                        queue.append((x,y+1,'R'))
                    if x+1<len(grid) and grid[x+1][y]==1:
                        grid[x+1][y]=0
                        queue.append((x+1,y,'D'))
                path.append('#')
            myset.add(''.join(path))
            
                
                            
                
                
            
        def numDistinctIslands(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            myset=set()
            for i in xrange(len(grid)):
                for j in xrange(len(grid[0])):
                    if grid[i][j]==1:
                        grid[i][j]=0
                        self.dfs(grid,[],deque([(i,j,'N')]),myset)
            print myset
            return len(myset)
            
    

Log in to reply
 

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