695. Max Area of Island

Loading...LeetCode

找岛问题都是一个套路...

200. Number of Islands130. Surrounded Regions

优先拿BFS做，简单点，每次找到新岛就queue下去，也可以DFS，把queue改成stack就算一种，或者换成recursive写法。

BFS

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return res
        
        res = 0
        m, n = len(grid), len(grid[0])
        memo = set()
        
        def validNext(x, y):
            valid = [(i, j )for (i, j) in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] if (i,j) not in memo and 0<= i<m and 0<=j<n]
            return valid
    
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if (x, y) in memo: continue
                if grid[x][y] == 1:
                    area = 0
                    q = collections.deque([(x, y)])
                    while q:
                        x_s, y_s = q.popleft()
                        memo.add((x_s, y_s))
                        area += 1
                        _next = validNext(x_s, y_s)
                        for x_n, y_n in _next:
                            memo.add((x_n, y_n))
                            if grid[x_n][y_n] == 1: q.append((x_n, y_n))
                    res = max(res, area)
        return res

DFS Recursive

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return res
        
        res = 0
        m, n = len(grid), len(grid[0])
        memo = set()
        
        def valid(x, y):
            if 0<=x<m and 0<=y<n and (x, y) not in memo: return True
        
        def dfs(x, y):
            if not valid(x, y) or grid[x][y] == 0: return 0
            memo.add((x, y))
            count = 1
            for x_n, y_n in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
                count += dfs(x_n, y_n)
            return count
    
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                area = dfs(x, y)
                res = max(res, area)
                
        return res