递归、搜索与回溯算法及 FloodFill 算法详解

递归、搜索与回溯算法及 FloodFill 算法详解

图像渲染 (LeetCode 733)

题目解析

给定一个二维整数数组 image，表示图像的像素值。给定起始坐标 (sr, sc) 和新颜色 newColor。从起始点开始，将相连的相同颜色的区域填充为新颜色。

算法原理

使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 遍历连通区域。核心是判断当前像素颜色是否与起始点颜色一致且未被访问过。

解法：暴搜 (DFS)

处理细节问题

如果原始像素值和要修改像素值相同 (image[sr][sc] == color)，直接返回即可，避免无限递归。

代码实现

def floodFill(image, sr, sc, newColor):
    original_color = image[sr][sc]
    if original_color == newColor:
        return image
    
    rows, cols = len(image), len(image[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    def dfs(r, c):
        if image[r][c] == original_color:
            image[r][c] = newColor
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    dfs(nr, nc)
    
    dfs(sr, sc)
    return image

注意： 本题不需要额外的 vis 数组标记走过的格子，因为修改后的颜色不再是 original_color，会被剪枝条件筛查掉。

---

岛屿数量 (LeetCode 200)

题目解析

给定由 '1'(陆地) 和 '0'(水) 组成的二维网格，计算岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

算法原理

遍历网格，遇到 '1' 时岛屿计数加一，并使用 DFS 将该岛屿所有相连的 '1' 标记为已访问（例如改为 '0'）。

解法：深度优先遍历

处理细节问题

• 剪枝条件：grid[x][y] == '1'，注意字符类型。
• ret++ 设置位置：在发现新岛屿起点时增加，而不是在每个格子查找完后。

代码实现

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # 标记为已访问
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in directions:
            dfs(r + dr, c + dc)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

思考： 为什么这道题不用恢复现场？ 因为我们要找出一块矩阵所有的联通区，这些联通区需要被记录（通过改变状态），且各个联通区不会出现重叠，所以在回溯时不需要也不能把记录过的联通区还原。

---

岛屿的最大面积 (LeetCode 695)

题目解析

同上题，但需要计算最大岛屿的面积。

算法原理

在 DFS 过程中累加当前连通区域的面积，并更新全局最大值。

代码实现

def maxAreaOfIsland(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    max_area = 0
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0  # 标记访问
        area = 1
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in directions:
            area += dfs(r + dr, c + dc)
        return area
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                current_area = dfs(i, j)
                max_area = max(max_area, current_area)
    
    return max_area

注意： count 不应设置为 dfs 的参数，否则回溯时会丢失部分统计结果，应作为局部变量返回累加值。

---

被围绕的区域 (LeetCode 130)

题目解析

给定一个二维矩阵，包含 'X' 和 'O'，将所有被 'X' 围绕的 'O' 替换为 'X'。

算法原理

正难则反。直接寻找被包围的区域较难，不如先找出与边界相连的 'O'，这些区域不会被包围。剩下的 'O' 即为被包围区域。

解法：反向标记

1. 扫描四条边，若遇到 'O'，从该点开始 DFS/BFS 标记所有连通的 'O'（例如改为 'A'）。
2. 遍历整个矩阵，将剩余的 'O' 改为 'X'，将 'A' 改回 'O'。

代码实现

def solve(board):
    if not board:
        return
    
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != 'O':
            return
        board[r][c] = 'A'
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in directions:
            dfs(r + dr, c + dc)
    
    # 标记边缘的 O
    for i in range(rows):
        dfs(i, 0)
        dfs(i, cols - 1)
    for j in range(cols):
        dfs(0, j)
        dfs(rows - 1, j)
    
    # 翻转剩余
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'A':
                board[i][j] = 'O'

---

太平洋大西洋水流问题 (LeetCode 417)

题目解析

给定一个 m x n 的非负整数矩阵，表示高度。水可以从高流向低或等高。找出既能流向太平洋（左/上边界）又能流向大西洋（右/下边界）的单元格。

算法原理

正难则反。从海洋边界逆着水流向上游搜索（从低到高）。分别找出能到达太平洋的所有点和能到达大西洋的所有点，取交集。

代码实现

def pacificAtlantic(heights):
    if not heights:
        return []
    
    rows, cols = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()
    
    def dfs(r, c, visited):
        visited.add((r, c))
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                if heights[nr][nc] >= heights[r][c]:
                    dfs(nr, nc, visited)
    
    # 从太平洋边界开始
    for i in range(rows):
        dfs(i, 0, pacific)
        dfs(i, cols - 1, atlantic)
    for j in range(cols):
        dfs(0, j, pacific)
        dfs(rows - 1, j, atlantic)
    
    return list(pacific & atlantic)

---

扫雷游戏 (LeetCode 529)

题目解析

根据点击位置揭示盘面。如果是地雷显示 'X'；如果是空格，显示周围地雷数；如果是空白且周围无雷，递归揭示周围 8 个格子。

算法原理

模拟游戏规则。使用 DFS 递归展开空白区域。注意八方向连通。

代码实现

def updateBoard(board, click):
    r, c = click
    if board[r][c] == 'M':
        board[r][c] = 'X'
        return board
    
    rows, cols = len(board), len(board[0])
    directions = [(i, j) for i in range(-1, 2) for j in range(-1, 2) if i != 0 or j != 0]
    
    def dfs(r, c):
        mine_count = 0
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'M':
                mine_count += 1
        
        if mine_count > 0:
            board[r][c] = str(mine_count)
        else:
            board[r][c] = 'B'
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'E':
                    dfs(nr, nc)
    
    dfs(r, c)
    return board

---

机器人的运动范围 (LeetCode 剑指 Offer 13)

题目解析

地上有一个 m 行 n 列的方格。机器人从 [0,0] 开始移动，每次向左、右、上、下移动一格。不能进入行坐标和列坐标的数位之和大于 k 的格子。

算法原理

深度优先遍历。定义辅助函数计算数位之和。使用 visited 数组防止重复统计。

代码实现

def movingCount(m, n, k):
    def digit_sum(num):
        s = 0
        while num > 0:
            s += num % 10
            num //= 10
        return s
    
    visited = [[False] * n for _ in range(m)]
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= m or c >= n or visited[r][c]:
            return 0
        if digit_sum(r) + digit_sum(c) > k:
            return 0
        
        visited[r][c] = True
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
    
    return dfs(0, 0)

注意： 必须定义标记数组，否则 ret 会统计重复走过的格子和递归回溯经过的格子的总数。