深度优先搜索 DFS

200. Number of Islands

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 将(i, j)的island转化为water
        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] == '0':
                return
            grid[i][j] = '0'
            for u, v in [i-1, j], [i+1, j], [i, j-1], [i, j+1]:
                dfs(u, v)
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    res += 1
        return res

• 时间复杂度：
• 空间复杂度：

bfs注意在加入队列之前，将岛屿置为0

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        num_islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    num_islands += 1
                    grid[i][j] = '0'                     # 1.陆地起始点
                    queue = collections.deque([(i, j)])
                    while queue:
                        r, c = queue.popleft()
                        for u, v in [r-1, c], [r+1, c], [r, c-1], [r, c+1]:
                            if 0 <= u < m and 0 <= v < n and grid[u][v] == '1':
                                grid[u][v] = '0'         # 2.陆地连接点
                                queue.append((u, v))
        return num_islands

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def bfs(i, j):
            queue = collections.deque([[i, j]])
            while queue:
                i, j = queue.popleft()
                if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                    grid[i][j] = '0'
                    queue += [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ans += 1
                    bfs(i, j)
        return ans

• 时间复杂度：
• 空间复杂度：

695. Max Area of Island

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] == 0:
                return 0
            grid[i][j] = 0
            return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
        m, n = len(grid), len(grid[0])
        max_area = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))
        return max_area

• 时间复杂度：
• 空间复杂度： ?

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_area = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    area = 1
                    grid[i][j] = 0
                    queue = collections.deque([(i, j)])
                    while queue:
                        r, c = queue.popleft()
                        for u, v in [r-1, c], [r+1, c], [r, c-1], [r, c+1]:
                            if 0 <= u < m and 0 <= v < n and grid[u][v] == 1:
                                area += 1
                                grid[u][v] = 0
                                queue.append((u, v))

                    max_area = max(max_area, area)

        return max_area