0130. 被围绕的区域 · ttttt

# 0130. 被围绕的区域 ## 题目地址(130. 被围绕的区域) <https://leetcode-cn.com/problems/surrounded-regions/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。示例: 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 解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。 ``` ``` ## 前置知识 - DFS ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路我们需要将所有被X包围的O变成X，并且题目明确说了边缘的所有O都是不可以变成X的。 ![](https://img.kancloud.cn/32/8b/328b6035231ad3235534e9f1789912ac_518x356.jpg) 其实我们观察会发现，我们除了边缘的O以及和边缘O连通的O是不需要变成X的，其他都要变成X。经过上面的思考，问题转化为连通区域问题。这里我们需要标记一下`边缘的O以及和边缘O连通的O`。我们当然可以用额外的空间去存，但是对于这道题目而言，我们完全可以mutate。这样就空间复杂度会好一点。整个过程如图所示： > 我将`边缘的O以及和边缘O连通的O` 标记为了 "A" ![](https://img.kancloud.cn/8f/f6/8ff6f2ea5a4aca4d433368a85713df35_819x405.jpg) ## 关键点解析 - 二维数组DFS解题模板 - 转化问题为`连通区域问题` - 直接mutate原数组，节省空间 ## 代码 - 语言支持：JS，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=130 lang=javascript * * [130] Surrounded Regions */ // 将O以及周边的O转化为A function mark(board, i, j, rows, cols) { if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O") return; board[i][j] = "A"; mark(board, i + 1, j, rows, cols); mark(board, i - 1, j, rows, cols); mark(board, i, j + 1, rows, cols); mark(board, i, j - 1, rows, cols); } /** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */ var solve = function(board) { const rows = board.length; if (rows === 0) return []; const cols = board[0].length; for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1) { mark(board, i, j, rows, cols); } } } for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (board[i][j] === "O") { board[i][j] = "X"; } else if (board[i][j] === "A") { board[i][j] = "O"; } } } return board; }; ``` ``` Python Code： ``` <pre class="calibre18">``` class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ # 如果数组长或宽小于等于2，则不需要替换 if len(board) <= 2 or len(board[0]) <= 2: return row, col = len(board), len(board[0]) def dfs(i, j): """ 深度优先算法，如果符合条件，替换为A并进一步测试，否则停止 """ if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O': return board[i][j] = 'A' dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) # 从外围开始 for i in range(row): dfs(i, 0) dfs(i, col-1) for j in range(col): dfs(0, j) dfs(row-1, j) # 最后完成替换 for i in range(row): for j in range(col): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == 'A': board[i][j] = 'O' ``` ``` ## 相关题目 - [200.number-of-islands](200.number-of-islands.html) > 解题模板是一样的 **复杂度分析** - 时间复杂度：O(row∗col)O(row \* col)O(row∗col) - 空间复杂度：O(row∗col)O(row \* col)O(row∗col) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经37K star啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)