目录
- 零、题目描述
- 一、为什么这道题值得你花时间掌握？
- 二、题目拆解：提取核心关键点
- 三、解题思路：从边界入手，反向标记
- 四、算法实现：深度优先遍历（DFS）+ 两次遍历
- 五、C++代码实现：一步步拆解
- 代码拆解
- 时间复杂度
- 空间复杂度
- 七、坑点总结
- 八、举一反三
- 九、总结
零、题目描述
题目链接：被围绕的区域
题目描述：
示例 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”]
]
解释：底部的'O'位于边缘，不被围绕，因此保留；其他'O'被'X'围绕，被替换为'X'。
示例 2：
输入：board = [[“X”]]
输出：[[“X”]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]为'X'或'O'
一、为什么这道题值得你花时间掌握？
如果你是第一次接触这类连通区域问题，强烈建议先按顺序看看我之前的两篇文章：《力扣 200. 岛屿数量》和《力扣 695. 岛屿的最大面积》。
这两篇就像“入门工具箱”：前者会手把手带你搞懂“怎么用DFS逛遍整个网格”“为啥要标记走过的路”，还有洪水灌溉算法最核心的框架；后者则在这基础上，教你怎么边逛边算面积、怎么盯紧最大的那块区域。先吃透这两篇，再看这篇博客时，面对递归方向、边界检查这些基础操作就不会懵了——毕竟这篇文章不会再重复讲这些啦，咱们重点聊更有意思的“思路升级”。
当然，如果你已经搞定前两题，那这道题对你来说就是个超棒的“进阶训练场”，值得花时间啃下来：
首先，它能让你彻底get到 “正难则反” 这种超好用的思维。前两题都是 “正面硬刚” —— 直接数岛屿、算面积，但这道题要是直接琢磨“哪些O被围住了”，保准越想越复杂。可反过来一想：“只要跟边缘的O连上，就肯定没被围住”，一下子就简单多了。这种“从对面找突破口”的思路，以后遇到复杂的连通问题，绝对能帮你少走很多弯路。
其次，它更像真实面试里会考察的样子。前两题主要看你会不会用DFS/BFS框架，而这道题还会悄悄观察你的“流程设计能力”：怎么用个临时标记区分特殊区域？怎么分两次遍历就把所有O安排明白？这些细节，恰恰是大厂想看出你是 “只会写代码”还是“真的懂算法” 的关键。
最后，学会它，以后遇到更复杂的题也能举一反三。比如「力扣 417. 太平洋大西洋水流问题」，要找那些“既能流进太平洋又能流进大西洋”的地方，要是正面一个个检查“这水能流到哪”，估计得算到天荒地老。但用这道题的思路反过来想：从两大洋的边上往回找，看哪些地方的水能够流到岸边，最后取个交集就行——你看，是不是跟这道题的反向思维如出一辙？
说白了，前两题是教你“认工具”，这道题是教你“灵活用工具解决麻烦事”。花点时间搞懂它，你的算法思维就能从“会操作”升级到“会策略”，绝对不亏～
二、题目拆解：提取核心关键点
我们来先看原题：
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：
· 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
· 区域：连接所有 ‘O’ 的单元格来形成一个区域。
· 围绕：如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。
通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。
再结合所给的代码框架和提示：
class Solution {
public:void solve(vector<vector<char>>& board) {}
};
要解决这道题，首先需要明确“被围绕的区域”的定义：不与矩阵边缘相连的所有’O’组成的区域，也就是上下左右被X包围的那个区域的O。反之，任何与边缘’O’相连的’O’都不会被围绕（因为边缘外不算’X’包围）。
核心要素提炼：
- 矩阵元素为 ‘X’（障碍）和 ‘O’（目标区域），长宽的范围是 1 ≤ m, n ≤ 200；
- 核心任务：区分“被围绕的 ‘O’”和“不被围绕的 ‘O’”，并将前者原地替换为 ‘X’；
- “被围绕”的判定标准：区域中所有 ‘O’ 均不与矩阵边缘（上、下、左、右边界）相连，且被 ‘X’ 包围。
关键点：
- 连通性规则：仅水平（左右）或垂直（上下）相邻的 ‘O’ 属于同一区域，斜对角不算，搜索时需遍历四个方向；
- 边界特殊性：任何与边缘 ‘O’ 相连的区域都不会被围绕（边缘外无 ‘X’ 包围）；
- DFS/BFS 搜索：需通过深度或广度优先遍历，标记与边缘相连的 ‘O’ 区域；
- 标记与替换策略：
- 用临时符号（如 ‘1’）标记“不被围绕的 ‘O’”（与边缘相连的区域）；
- 遍历矩阵，将未标记的 ‘O’ 替换为 ‘X’，将临时标记的 ‘1’ 恢复为 ‘O’；
- 边界处理：搜索时需检查坐标合法性（0 ≤ x < 行数 且 0 ≤ y < 列数），防止越界。
与前两题（岛屿数量、岛屿最大面积）的共性（可复用的逻辑）：
- 遍历框架：通过双重循环遍历每个单元格，发现目标元素（前两题是 ‘1’，本题是边缘 ‘O’）时触发搜索；
- DFS 核心逻辑：递归遍历上下左右四个方向，处理连通区域；
- 标记访问：通过修改原矩阵元素（前两题标记为 ‘0’，本题标记为 ‘1’）避免重复访问；
- 方向数组：用
dx = [1,-1,0,0]、dy = [0,0,1,-1]定义四个方向，简化坐标计算。
关键差异（本次重点掌握的新逻辑）：
-
从“正向搜索目标”到“反向标记安全区”：
- 前两题直接搜索目标区域（岛屿）并计数/算面积；
- 本题先标记“不被围绕的 ‘O’”（与边缘相连的区域），再通过排除法处理“被围绕的 ‘O’”。
-
两次遍历的流程设计：
- 第一次遍历：从边缘 ‘O’ 出发，用 DFS 标记所有相连的 ‘O’ 为 ‘1’（安全区）；
- 第二次遍历：遍历整个矩阵，完成替换（‘O’→’X’，‘1’→’O’）。
-
标记符号的选择：
- 前两题用 ‘0’ 标记已访问的 ‘1’（覆盖原元素不影响结果）；
- 本题需用矩阵中不存在的符号（如 ‘1’）作为临时标记，避免与原元素冲突，最后需恢复为 ‘O’。
三、解题思路：从边界入手，反向标记
题目拆解中也提到了这道题和前两题“地毯式搜索所有区域”的思路不同，这道题的突破口就是边缘的’O’ 里——只要挨着边缘的’O’，那它肯定没被围住，这是板上钉钉的事儿。
要是按正常思路硬刚：写个DFS去搜每个’O’，判断它是不是该被改成’X’，估计会头大到想掀桌子——我当时就卡了20多分钟，越想越乱：
- 怎么判断一个’O’到底挨没挨边界？总不能搜着搜着突然回头查坐标吧？
- 就算搜到了边界，怎么告诉上层递归“这一片都不能改”？难道要搞多个递归函数分别处理？
- 递归的终止条件更是一团乱麻：是先判断边界还是先标记？一步错步步错。
后来才反应过来：换个角度不就完了？既然边缘的’O’和它的“朋友圈”都安全，那先把它们圈出来，接下来就收拾没有被圈出来的“小可爱们”不就可以了？
核心逻辑：先标记，再清场
- 第一步：给“边缘”贴标记
沿着矩阵的四条边遍历，但凡看到’O’，就用DFS遍历下，把所有跟它连着的’O’都改为临时符号标记（比如改成’1’）。这些贴了标签的，都是“背景硬”的安全区，绝对不能动。
- 第二步：大扫除，分情况处理
再从头到尾扫一遍矩阵：- 没被标记的’O’：妥妥的“要被处理的”，全改成’X’；
- 被标记的’1’：把进士标记改回去，恢复成’O’——毕竟它们本来就是O。
和前两题的思路对比：
| 题目 | 核心操作 | 标记目的 | 遍历次数 |
|---|---|---|---|
| 岛屿数量 | 发现’O’则计数并淹没 | 避免重复计数 | 1次 |
| 岛屿最大面积 | 发现’O’则计算面积并淹没 | 避免重复计算 | 1次 |
| 被围绕的区域 | 先用临时符号标记边缘连通区，再替换 | 区分安全区和被围绕区 | 2次 |
你看，前两题是“发现一个处理一个”，这题是“先圈范围再批量处理”——思路一换，复杂题立马变简单~
四、算法实现：深度优先遍历（DFS）+ 两次遍历
基于上述思路，我们用DFS实现标记，用两次遍历完成替换。下面是具体步骤：
- 边缘遍历：遍历矩阵的四条边（i=0、i=rows-1、j=0、j=cols-1），对每个’O’调用DFS；
- DFS标记：在DFS中，将当前’O’标记为’1’，并递归处理上下左右四个方向的相邻’O’；
- 全局替换：遍历整个矩阵，按规则替换字符（‘O’→’X’，‘1’→’O’）。
五、C++代码实现：一步步拆解
下面结合代码详细说明：
class Solution {
public:int rows, cols; // 矩阵的行数和列数// 方向数组：上下左右四个方向（与岛屿问题相同）int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};void solve(vector<vector<char>>& board) {if (board.empty()) return; // 边界处理：空矩阵直接返回rows = board.size();cols = board[0].size();// 第一步：遍历四条边缘，标记所有与边缘相连的'O'为'1'// 遍历上下边缘（i=0 和 i=rows-1，j从0到cols-1）for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') dfs(0, j, board);if (board[rows-1][j] == 'O') dfs(rows-1, j, board);}// 遍历左右边缘（j=0 和 j=cols-1，i从1到rows-2，避免重复遍历角落）for (int i = 1; i < rows-1; i++) {if (board[i][0] == 'O') dfs(i, 0, board);if (board[i][cols-1] == 'O') dfs(i, cols-1, board);}// 第二步：遍历整个矩阵，替换字符for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == '1') {// 恢复安全区域为'O'board[i][j] = 'O';} else if (board[i][j] == 'O') {// 未标记的'O'是被围绕的，替换为'X'board[i][j] = 'X';}}}}// DFS：将与边缘相连的'O'标记为'1'void dfs(int x, int y, vector<vector<char>>& board) {// 标记当前位置为'1'（临时标记，代表安全区域）board[x][y] = '1';// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i]; // 新行坐标int ny = y + dy[i]; // 新列坐标// 检查边界合法性，且相邻位置是未标记的'O'if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && board[nx][ny] == 'O') {dfs(nx, ny, board); // 递归标记}}}
};
代码拆解
1. 类成员变量解析
int rows, cols; // 存储矩阵的行数和列数，避免在DFS中重复计算
int dx[4] = {1, -1, 0, 0}; // 方向偏移：下、上、右、左
int dy[4] = {0, 0, 1, -1}; // 配合dx实现四个方向的坐标计算
- 方向数组与前两题完全一致，复用“上下左右”的遍历逻辑；
rows和cols在solve中初始化，确保DFS中能快速判断边界。
2. solve函数核心流程
第一步：边缘遍历与标记
// 遍历上下边缘（i=0和i=rows-1）
for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') dfs(0, j, board);if (board[rows-1][j] == 'O') dfs(rows-1, j, board);
}
// 遍历左右边缘（j=0和j=cols-1，跳过已遍历的角落）
for (int i = 1; i < rows-1; i++) {if (board[i][0] == 'O') dfs(i, 0, board);if (board[i][cols-1] == 'O') dfs(i, cols-1, board);
}
- 为什么分两次遍历？
上下边缘的角落（如(0,0)）会被i=0和j=0重复检查，但DFS中会标记为’1’，第二次检查时board[i][j]已不是’O’，因此不会重复递归，无需额外判断。
第二步：全局替换
for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == '1') board[i][j] = 'O'; // 恢复安全区域else if (board[i][j] == 'O') board[i][j] = 'X'; // 替换被围绕区域}
}
- 这一步是解题的“收尾”：通过一次遍历完成两种替换，逻辑清晰且高效。
3. dfs函数核心逻辑
void dfs(int x, int y, vector<vector<char>>& board) {board[x][y] = '1'; // 立即标记为安全区域for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];// 边界合法且是未标记的'O'才递归if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && board[nx][ny] == 'O') {dfs(nx, ny, board);}}
}
- 标记时机：进入DFS后立即将’O’改为’1’，避免同一单元格被多次递归（与前两题“立即淹没”逻辑一致）；
- 递归条件：仅对“在边界内”且“未标记的’O’”递归，确保不越界且不重复处理。
示例运行过程（以示例1为例）
输入矩阵：
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]
]
第一步：边缘遍历
- 下边缘（i=3）的(j=1)是’O’，触发DFS：
- 标记(3,1)为’1’，检查四周：上方(2,1)是’X’，其他方向无’O’，DFS结束。
此时矩阵变为：
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","1","X","X"]
]
第二步：全局替换
- 遍历所有单元格：
- (1,1)、(1,2)、(2,2)是’O’→替换为’X’；
- (3,1)是’1’→恢复为’O’。
最终结果：
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]
]
时间复杂度
| 操作步骤 | 具体分析 | 时间复杂度 |
|---|---|---|
| 边缘遍历 | 最多访问4×max(m,n)个单元格（四条边缘的总长度） | O(m+n) |
| DFS标记安全区 | 每个’O’最多被访问1次（标记为’1’后不再处理） | O(m×n) |
| 全局替换操作 | 遍历整个矩阵的m×n个单元格，执行替换逻辑 | O(m×n) |
| 总计 | 所有操作的总次数与矩阵大小（m×n）成正比 | O(m×n) |
空间复杂度
| 消耗场景 | 具体分析 | 空间复杂度 |
|---|---|---|
| DFS递归栈 | 最坏情况（全为’O’且边缘有’O’）：递归深度可达m×n（如200×200全’O’矩阵） | O(m×n) |
| 原地修改存储 | 无需额外数据结构，直接修改原矩阵（用’1’临时标记） | O(1) |
| 总计 | 空间消耗由递归栈深度决定，最坏情况下与矩阵大小成正比 | O(m×n) |
七、坑点总结
-
边缘遍历不完整
❌错误：只遍历上下边缘或左右边缘，漏掉角落的’O’（如(0,0)）。
✅解决：必须遍历四条边（i=0、i=rows-1、j=0、j=cols-1），确保所有边缘’O’都被处理。 -
临时标记与原字符冲突
❌错误：用’O’或’X’作为临时标记（如误将安全区域标记为’O’，导致无法区分）。
✅解决：使用矩阵中不存在的字符（如’1’、'#'等）作为临时标记，避免冲突。 -
DFS边界检查顺序
❌错误：先判断board[nx][ny] == 'O'，再检查坐标是否越界（可能导致访问无效坐标）。
✅解决：先检查坐标合法性（nx和ny是否在0rows-1和0cols-1范围内），再判断字符是否为’O’。 -
替换逻辑颠倒
❌错误：将’1’替换为’X’，将’O’替换为’O’（完全错误）。
✅解决：明确替换规则：'1'→'O'（恢复安全区），'O'→'X'（替换被围绕区）。
八、举一反三
掌握本题思路后，可解决以下类似问题，尤其是那些需要“反向标记”或“边界连通性判断”的场景：
-
LeetCode 417. 太平洋大西洋水流问题
问题：找到既能流向太平洋，又能流向大西洋的所有单元格。
思路：用本题“反向标记”的升级版——从太平洋边缘（上、左）和大西洋边缘（下、右）分别出发，标记所有能流向两大洋的单元格，最后取交集。这种“从结果倒推起点”的逻辑，与本题的反向思维如出一辙。 -
LeetCode 1020. 飞地的数量
问题：计算无法从边界离开的陆地（‘1’）的数量。
思路：与本题类似，先标记所有与边界相连的’1’（可离开的），再统计未标记的’1’（飞地）数量，核心是“排除法”思维。 -
LeetCode 529. 扫雷游戏
问题：根据点击位置，展开所有无地雷的连通区域。
思路：通过DFS/BFS从点击位置出发，按规则标记并展开区域，考验“条件递归”和“边界处理”，与本题的搜索框架高度契合。
这些问题虽场景不同，但核心都离不开“连通区域标记”和“边界特殊性利用”，掌握本题思路后，再解这些题会有种“一通百通”的感觉～
九、总结
「被围绕的区域」是连通区域问题中对“边界特殊性”考察的典型题目。它的核心思维是 “从边缘反向标记安全区域，再通过一次遍历完成状态转换”，这与前两题的“正向搜索”形成互补。
解题的关键不是记住代码，而是理解：
- 如何通过边界特征（是否接触边缘）定义区域性质；
- 如何用临时标记区分不同区域；
- 如何设计两次遍历实现原地修改。
掌握这些，你就能应对所有“基于边界的连通区域划分”问题，面试中再遇到类似题目也能游刃有余。
最后欢迎大家在评论区分享你的代码或思路，咱们一起交流探讨~ 🌟 要是有大佬有更精妙的思路或想法，恳请在评论区多多指点批评，我一定会虚心学习，并且第一时间回复交流哒！
这是封面原图～ 喜欢的话先点个赞鼓励一下呗～ 再顺手关注一波，后续更新不迷路，保证让你看得过瘾！😉
)
