❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
解读力扣第 130 题：被围绕的区域
在本篇文章中，我们将详细解读力扣第 130 题“被围绕的区域”。通过学习本篇文章，读者将掌握如何使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决二维网格问题的技巧。
问题描述
力扣第 130 题“被围绕的区域”描述如下：
给你一个
m x n的二维矩阵board，由'X'和'O'组成。找到所有被'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。
示例 1:
输入: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] 输出: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
示例 2:
输入: board = [["X"]] 输出: [["X"]]
解题思路
- 初步分析：
- 我们需要找到所有被
'X'围绕的'O'区域，并将这些'O'替换为'X'。 - 如果一个
'O'位于边界上或连接到边界上的'O'，则不能被替换。
- DFS/BFS方法：
- 我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来标记从边界上开始的
'O'，这些'O'不能被替换。 - 然后遍历整个网格，将未标记的
'O'替换为'X'，标记的'O'恢复原状。
代码实现
解法一：深度优先搜索（DFS）方法
- 步骤：
- 从网格的四个边界开始，进行DFS，将连接到边界的
'O'标记为临时字符'T'。 - 遍历整个网格，将未被标记的
'O'替换为'X'，将标记的'T'恢复为'O'。
- 伪代码：
def dfs(board, i, j): if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O': return board[i][j] = 'T' dfs(board, i + 1, j) dfs(board, i - 1, j) dfs(board, i, j + 1) dfs(board, i, j - 1)
代码实现
def solve(board): if not board or not board[0]: return m, n = len(board), len(board[0]) def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O': return board[i][j] = 'T' dfs(i + 1, j) dfs(i - 1, j) dfs(i, j + 1) dfs(i, j - 1) # 从边界开始DFS，将所有连接的'O'标记为'T' for i in range(m): dfs(i, 0) dfs(i, n - 1) for j in range(n): dfs(0, j) dfs(m - 1, j) # 遍历整个网格，将未被标记的'O'替换为'X'，将标记的'T'恢复为'O' for i in range(m): for j in range(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'T': board[i][j] = 'O' # 测试案例 board1 = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] solve(board1) print(board1) # [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] board2 = [["X"]] solve(board2) print(board2) # [["X"]]
复杂度分析
- 时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数。每个点最多被访问两次。
- 空间复杂度：O(m * n)，递归调用栈的最大深度。
代码优化
解法二：广度优先搜索（BFS）方法
- 步骤：
- 使用队列从边界开始进行广度优先搜索（BFS），将连接到边界的
'O'标记为临时字符'T'。 - 遍历整个网格，将未被标记的
'O'替换为'X'，将标记的'T'恢复为'O'。
- 伪代码：
def bfs(board, i, j): queue.append((i, j)) while queue: x, y = queue.pop(0) if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != 'O': continue board[x][y] = 'T' queue.append((x + 1, y)) queue.append((x - 1, y)) queue.append((x, y + 1)) queue.append((x, y - 1))
代码实现
from collections import deque def solve(board): if not board or not board[0]: return m, n = len(board), len(board[0]) def bfs(i, j): queue = deque([(i, j)]) while queue: x, y = queue.popleft() if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != 'O': continue board[x][y] = 'T' queue.append((x + 1, y)) queue.append((x - 1, y)) queue.append((x, y + 1)) queue.append((x, y - 1)) # 从边界开始BFS，将所有连接的'O'标记为'T' for i in range(m): bfs(i, 0) bfs(i, n - 1) for j in range(n): bfs(0, j) bfs(m - 1, j) # 遍历整个网格，将未被标记的'O'替换为'X'，将标记的'T'恢复为'O' for i in range(m): for j in range(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'T': board[i][j] = 'O' # 测试案例 board1 = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] solve(board1) print(board1) # [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] board2 = [["X"]] solve(board2) print(board2) # [["X"]]
复杂度分析
- 时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数。每个点最多被访问两次。
- 空间复杂度：O(min(m, n))，用于队列存储的空间。
总结
本文详细解读了力扣第 130 题“被围绕的区域”，通过深度优先搜索（DFS）和广度优先搜索（BFS）两种不同的解法，帮助读者深入理解二维网格问题的解决思路。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
