深入讲解了递归、搜索与回溯算法在二维矩阵中的应用，重点剖析了 FloodFill 算法及其变体。内容涵盖图像渲染、岛屿数量、岛屿最大面积、被围绕的区域、太平洋大西洋水流问题、扫雷游戏以及机器人的运动范围等经典 LeetCode 题目。文章详细阐述了深度优先搜索 (DFS) 的核心逻辑，包括连通区域标记、边界处理、逆向思维优化（如正难则反策略）、以及何时需要恢复现场等关键细节，并提供了完整的 Python 代码实现与注意事项总结。
给定一个二维整数数组 image，表示图像的像素值。给定起始坐标 (sr, sc) 和新颜色 newColor。从起始点开始，将相连的相同颜色的区域填充为新颜色。
使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 遍历连通区域。核心是判断当前像素颜色是否与起始点颜色一致且未被访问过。
如果原始像素值和要修改像素值相同 (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，会被剪枝条件筛查掉。
给定由 '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
思考： 为什么这道题不用恢复现场？ 因为我们要找出一块矩阵所有的联通区，这些联通区需要被记录（通过改变状态），且各个联通区不会出现重叠，所以在回溯时不需要也不能把记录过的联通区还原。
同上题，但需要计算最大岛屿的面积。
在 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 的参数，否则回溯时会丢失部分统计结果，应作为局部变量返回累加值。
给定一个二维矩阵，包含 'X' 和 'O'，将所有被 'X' 围绕的 'O' 替换为 'X'。
正难则反。直接寻找被包围的区域较难，不如先找出与边界相连的 'O'，这些区域不会被包围。剩下的 'O' 即为被包围区域。
'O'，从该点开始 DFS/BFS 标记所有连通的 'O'（例如改为 'A'）。'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'
board[i][j] == :
board[i][j] =
给定一个 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)
根据点击位置揭示盘面。如果是地雷显示 '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)
board
地上有一个 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 会统计重复走过的格子和递归回溯经过的格子的总数。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online