leetcode695 岛屿的最大面积

使用dfs,遍历grid当为1的时候，就通过dfs看这个岛屿的面积有多大，最后比较选出最大的一个。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(x,y,visit,count):
            if grid[x][y]==1:
                visit[x][y]=1
                count+=1
            else:
                return count

            for item in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and visit[x+item[0]][y+item[1]]!=1 and grid[x+item[0]][y+item[1]]!=0:

                    count=dfs(x+item[0],y+item[1],visit,count)
            return count

        maxvalue=0

        visit=[[0]*len(grid[0]) for _ in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                   maxvalue=max(maxvalue, dfs(i,j,visit,0))
        return maxvalue

使用栈，可以类比使用队列。

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


        stack=[]
        maxvalue=0

        for i in range(len(grid)):
            for j in range(len(grid[0])):

                if grid[i][j]==1:
                    count=1
                    grid[i][j]=0
                    stack.append((i,j))
                    while stack:
                        x,y=stack.pop()
                        for item in [(1,0),(0,1),(-1,0),(0,-1)]:
                            if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and grid[x+item[0]][y+item[1]]==1:
                                grid[x+item[0]][y+item[1]]=0
                                stack.append((x+item[0],y+item[1]))
                                count+=1
                    maxvalue=max(maxvalue,count)

        return maxvalue

使用队列，只把栈的pop()改成pop(0)即可。

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


        stack=[]
        maxvalue=0

        for i in range(len(grid)):
            for j in range(len(grid[0])):

                if grid[i][j]==1:
                    count=1
                    grid[i][j]=0
                    stack.append((i,j))
                    while stack:
                        x,y=stack.pop(0)
                        for item in [(1,0),(0,1),(-1,0),(0,-1)]:
                            if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and grid[x+item[0]][y+item[1]]==1:
                                grid[x+item[0]][y+item[1]]=0
                                stack.append((x+item[0],y+item[1]))
                                count+=1
                    maxvalue=max(maxvalue,count)

        return maxvalue