提示

适用于需要计算连通块个数、大小的题目。

部分题目也可以用 BFS 或并查集解决。

阿囧：挺像扫雷的（

1. 200. 岛屿数量

   class Solution:
   def numIslands(self, grid: List[List[str]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != '1': # 地图外面或者非陆地就返回
               return
           grid[i][j] = '2' # 是陆地，插旗
           dfs(i - 1, j) # 其他四个方向走走
           dfs(i + 1, j)
           dfs(i, j - 1)
           dfs(i, j + 1)
   
       res = 0
       for i, row in enumerate(grid):
           for j, c in enumerate(row):
               if c == '1': # 发现岛屿
                   res += 1
                   dfs(i, j) # 占领此岛，插满旗子 '2'
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

2. 695. 岛屿的最大面积

   class Solution:
   def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:
               return 0
           grid[i][j] = 2
           return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
   
       res = 0
       for i, row in enumerate(grid):
           for j, c in enumerate(row):
               if grid[i][j] == 1:
                   res = max(res, dfs(i, j))
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

3. 面试题 16.19. 水域大小

   注意此题是 8 方向，这题才是扫雷，but who care ? 一力破万法

   class Solution:
   def pondSizes(self, land: List[List[int]]) -> List[int]:
       m, n = len(land), len(land[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or land[i][j] != 0:
               return 0
           land[i][j] = 1
           return 1 + dfs(i - 1, j - 1) + dfs(i - 1, j) + dfs(i - 1, j + 1) + dfs(i, j - 1) + dfs(i, j + 1) + dfs(i + 1, j - 1) + dfs(i + 1, j) + dfs(i + 1, j + 1)
   
       res = []
       for i, row in enumerate(land):
           for j, c in enumerate(row):
               if land[i][j] == 0:
                   res.append(dfs(i, j))
       res.sort()
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 land 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

4. LCS 03. 主题空间

   class Solution:
   def largestArea(self, grid: List[str]) -> int:
       grid = [list(i) for i in grid]
       m, n = len(grid), len(grid[0])
       def dfs(i,j):
           nonlocal now
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == '0': # 外面和里面0元素
               return float('-inf')
           if grid[i][j]== now: # 现在只剩下里面非0元素，找到是同一主题的
               grid[i][j] = "6"
               return dfs(i+1,j) + dfs(i-1,j)+ dfs(i,j-1)+dfs(i,j+1) + 1
           else:
               return 0
           
       res = 0
       for i, row in enumerate(grid):
           for j, c in enumerate(row):
               now = grid[i][j]
               if c != '0' and c != '6':
                   res = max(res, dfs(i, j))
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

5. 463. 岛屿的周长

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

6. 2658. 网格图中鱼的最大数目

   class Solution:
   def findMaxFish(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >=m or j >= n or grid[i][j] <= 0:
               return 0
           fish = grid[i][j]
           grid[i][j] = -1
           return fish + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
   
       res = 0
       for i, row in enumerate(grid):
           for j, c in enumerate(row):
               if c > 0:
                   res = max(res, dfs(i, j))
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

7. 2658. 网格图中鱼的最大数目

   class Solution:
   def findMaxFish(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >=m or j >= n or grid[i][j] <= 0:
               return 0
           fish = grid[i][j]
           grid[i][j] = -1
           return fish + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
   
       res = 0
       for i, row in enumerate(grid):
           for j, c in enumerate(row):
               if c > 0:
                   res = max(res, dfs(i, j))
       return res

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

8. 1034. 边界着色

   class Solution:
   def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
       visited = set()
       border = []
       target = grid[row][col]
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != target: # 不是连通的，返回False
               return False
           
           if (i, j) in visited:
               return True
           
           visited.add((i, j))
   
           is_border = False # 默认不是边界
   
           for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 遍历上下左右
               if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] != target:
                   is_border = True # 如果旁边越界或者是其他颜色了，说明是边界
               else:
                   if dfs(x, y): # 如果是连通的，遍历他
                       continue
           if is_border:
               border.append((i, j))
   
           return True # 是连通的
   
       dfs(row, col)
       for i, j in border:
           grid[i][j] = color
       return grid

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

9. 1020. 飞地的数量

   思路：直接遍历矩阵的边界，发现陆地，就去dfs，把与其相连的陆地（包括边界自己）都变成海洋，最后统计矩阵中剩余的陆地就是答案

   class Solution:
   def numEnclaves(self, grid: List[List[int]]) -> int:
       m, n = len(grid), len(grid[0])
       def dfs(i, j):
           if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1: # 外面和非1
               return
           grid[i][j] = 0
           dfs(i - 1, j)
           dfs(i + 1, j)
           dfs(i, j - 1)
           dfs(i, j + 1)
   
       for i in range(m):
           if grid[i][0]:
               dfs(i, 0)
           if grid[i][n - 1]:
               dfs(i, n - 1)
   
       for j in range(n):
           if grid[0][j]:
               dfs(0, j)
           if grid[m - 1][j]:
               dfs(m - 1, j)
       return sum(sum(g) for g in grid)

   时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

   空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

10. 2684. 矩阵中移动的最大次数

    class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
    
        def dfs(i, j):
            nonlocal res
            res = max(res, j)
            if j == n - 1:
                return
            
            for k in i - 1, i, i + 1:
                if 0 <= k < m and grid[k][j + 1] > grid[i][j]:
                    dfs(k, j + 1)
    
            grid[i][j] = 0 # 避免下面的走重复的路
    
        res = 0
        for i in range(m):
            dfs(i, 0)
        return res

    时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

11. 1254. 统计封闭岛屿的数目

    有点意思，方法一：用一个变量标记本次遍历是否是边界，不是边界才加一

    class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            nonlocal is_close
            if i < 0 or j < 0 or i >= m or j >= n:
                is_close = False
                return
            if grid[i][j] != 0:
                return
            grid[i][j] = 2
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                dfs(x, y)
    
        res = 0
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                is_close = True
                if c == 0:
                    dfs(i, j)
                    if is_close:
                        res += 1
        return res

    时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

    方法二：先外后内，把边界上连通的都变成海洋，再去正常二重 for 循环

    class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if m < 3 or n < 3: return 0
    
        def dfs(x: int, y: int) -> None:
            grid[x][y] = 1  # 标记 (x,y) 被访问，避免重复访问
            # 访问四方向的 0
            for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
                if 0 <= i < m and 0 <= j < n and grid[i][j] == 0:
                    dfs(i, j)
    
        for i in range(m):
            # 如果是第一行和最后一行，访问所有格子
            # 如果不是，只访问第一列和最后一列的格子
            step = 1 if i == 0 or i == m - 1 else n - 1
            for j in range(0, n, step):
                if grid[i][j] == 0:  # 从没有访问过的 0 出发
                    dfs(i, j)
    
        ans = 0
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 0:  # 从没有访问过的 0 出发
                    ans += 1  # 一定是封闭岛屿
                    dfs(i, j)
        return ans

    时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

12. 130. 被围绕的区域

    从边界出发，先把边界上和 O 连通点找到, 把这些变成 B,然后遍历整个 board 把 O 变成 X, 把 B 变成 O

    

    class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        is_x = [["X"] * n for _ in range(m)]
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != "O":
                return
            is_x[i][j] = "O"
            board[i][j] = "B"
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                dfs(x, y)
    
        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n - 1] == 'O':
                dfs(i, n - 1)
    
        for j in range(n):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[m - 1][j] == 'O':
                dfs(m - 1, j)
    
        
        for i, row in enumerate(board):
            for j, c in enumerate(row):
                if c == "O":
                    board[i][j] = "X"
                elif c == "B":
                    board[i][j] = "O"

    时间复杂度：O(mn)，其中 m 和 n 分别为 board 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

13. 1905. 统计子岛屿

    思路：正常 dfs 遍历 grid2 ，每次遍历陆地 grid2[i][j] 的时候要去查询一下 grid1[i][j] 是不是陆地，如果 grid1[i][j] 不是陆地，那么 is_islands 设置为 False ，不计入岛屿总和 res 。

    class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
    
        m, n = len(grid1), len(grid1[0])
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] != 1:
                return
            grid2[i][j] = 2
            nonlocal is_islands
            if grid1[i][j] == 0:
                is_islands = False
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                dfs(x, y)
    
        res = 0
        for i, row in enumerate(grid2):
            for j, c in enumerate(row):
                if c == 1:
                    is_islands = True
                    dfs(i, j)
                    if is_islands:
                        res += 1
        return res

    时间复杂度：O(mn)，其中 m 和 n 分别为 grid1 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。

14. 1391. 检查网格中是否存在有效路径

    思路：开辟和二维矩阵 grid 一样大的二维矩阵 is_arrive 来存放哪些地方可以到达，初始全 False ，写一个 connect 函数判断下一个位置 (x, y) 和当前是否连通，如果连通且未访问过，那么进入 dfs ，最后返回 is_arrive 的最后一个点的真值即可。

    class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        is_arrive = [[False] * n for _ in range(m)]
        def dfs(i, j):
            is_arrive[i][j] = True
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < m and 0 <= y < n and connect(i, j, x, y) and not is_arrive[x][y]:
                    dfs(x, y)
    
        def connect(i, j, x, y):
            if x == i + 1 and grid[i][j] in [2, 3, 4] and grid[x][y] in [2, 5, 6]:
                return True
            if x == i - 1 and grid[i][j] in [2, 5, 6] and grid[x][y] in [2, 3, 4]:
                return True
            if y == j + 1 and grid[i][j] in [1, 4, 6] and grid[x][y] in [1, 3, 5]:
                return True
            if y == j - 1 and grid[i][j] in [1, 3, 5] and grid[x][y] in [1, 4, 6]:
                return True
            return False
            
        dfs(0, 0)
        return is_arrive[-1][-1]

    时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。

    空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。