leetcode827 最大人工岛

dfs 超时
通过遍历时设置不同的标志，来遍历，也可以通过栈。
时间复杂度：O(N^4)O(N
4
)，其中 NN 是 grid 的长和宽。
空间复杂度：O(N^2)O(N
2
)，深度优先搜索需要的 stack 和 seen 的空间。

作者：LeetCode
链接：https://leetcode-cn.com/problems/making-a-large-island/solution/zui-da-ren-gong-dao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:

        def dfs(x,y,visit,count,num):


            grid[x][y]=num
            for item in [(1,0),(0,1),(0,-1),(-1,0)]:
                cur_x=x+item[0]
                cur_y=y+item[1]

                if 0<=cur_x<len(grid) and 0<=cur_y<len(grid[0]) and grid[cur_x][cur_y]!=num and grid[cur_x][cur_y]!=0:

                    count+=1

                    count=dfs(cur_x,cur_y,visit,count,num)


            return count

        maxvalue=0
        count=0
        visit=[[0]*len(grid[0]) for _ in range(len(grid))]
        num=2
        for i in range(len(grid)):
            for j in range(len(grid[0])):

                if grid[i][j]==0:

                    grid[i][j]=1
                    print(grid)
                    count=dfs(i,j,visit,1,num)
                    grid[i][j]=0

                    num+=1

                    maxvalue=max(maxvalue,count)
        if maxvalue==0:
            return len(grid)*len(grid[0])
        return maxvalue

通过一次dfs得到所有连通的数量，将连通的位置标记上序号从2开始，因为0，1有意义的，然后遍历为0的位置，看他的上下左右是否有连通的组织，序号不一致的放入数组中，这里可以通过set控制，然后将set中的对应连通组织面积加和，注意数量不限，最后加上1，这里要判断下全1和全0的状态。

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:

        def dfs(x,y,visit,count,num):


            grid[x][y]=num
            for item in [(1,0),(0,1),(0,-1),(-1,0)]:
                cur_x=x+item[0]
                cur_y=y+item[1]

                if 0<=cur_x<len(grid) and 0<=cur_y<len(grid[0]) and grid[cur_x][cur_y]==1:

                    count+=1

                    count=dfs(cur_x,cur_y,visit,count,num)


            return count

        maxvalue=0
        count=0
        visit=[[0]*len(grid[0]) for _ in range(len(grid))]
        num=2
        hashmap=collections.defaultdict(int)
        hashset=set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):

                if grid[i][j]==1:


                    count=dfs(i,j,visit,1,num)
                    #print(grid)
                    hashmap[num]=count


                    num+=1

                    maxvalue=max(maxvalue,count)
        if maxvalue==0:
            return 1
        if maxvalue==len(grid)*len(grid[0]):
            return len(grid)*len(grid[0])
        area=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==0:
                    hashset=set()
                    for item in [(1,0),(0,1),(-1,0),(0,-1)]:
                        if 0<=i+item[0]<len(grid) and 0<=j+item[1]<len(grid[0])and grid[i+item[0]][j+item[1]]!=0:
                            hashset.add(grid[i+item[0]][j+item[1]])
                    area=0
                    for k in hashset:

                        area+=hashmap[k]
                    area+=1

                maxvalue=max(maxvalue,area)                

        return maxvalue