面试高频题 力扣 130. 被围绕的区域 洪水灌溉(FloodFill) 深度优先遍历(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’ 包围。

关键点：

1. 连通性规则：仅水平（左右）或垂直（上下）相邻的 ‘O’ 属于同一区域，斜对角不算，搜索时需遍历四个方向；
2. 边界特殊性：任何与边缘 ‘O’ 相连的区域都不会被围绕（边缘外无 ‘X’ 包围）；
3. DFS/BFS 搜索：需通过深度或广度优先遍历，标记与边缘相连的 ‘O’ 区域；
4. 标记与替换策略：
   • 用临时符号（如 ‘1’）标记“不被围绕的 ‘O’”（与边缘相连的区域）；
   • 遍历矩阵，将未标记的 ‘O’ 替换为 ‘X’，将临时标记的 ‘1’ 恢复为 ‘O’；
5. 边界处理：搜索时需检查坐标合法性（0 ≤ x < 行数 且 0 ≤ y < 列数），防止越界。

与前两题（岛屿数量、岛屿最大面积）的共性（可复用的逻辑）：

1. 遍历框架：通过双重循环遍历每个单元格，发现目标元素（前两题是 ‘1’，本题是边缘 ‘O’）时触发搜索；
2. DFS 核心逻辑：递归遍历上下左右四个方向，处理连通区域；
3. 标记访问：通过修改原矩阵元素（前两题标记为 ‘0’，本题标记为 ‘1’）避免重复访问；
4. 方向数组：用 dx = [1,-1,0,0]、dy = [0,0,1,-1] 定义四个方向，简化坐标计算。

关键差异（本次重点掌握的新逻辑）：

1. 从“正向搜索目标”到“反向标记安全区”：

   • 前两题直接搜索目标区域（岛屿）并计数/算面积；
   • 本题先标记“不被围绕的 ‘O’”（与边缘相连的区域），再通过排除法处理“被围绕的 ‘O’”。

2. 两次遍历的流程设计：

   • 第一次遍历：从边缘 ‘O’ 出发，用 DFS 标记所有相连的 ‘O’ 为 ‘1’（安全区）；
   • 第二次遍历：遍历整个矩阵，完成替换（‘O’→’X’，‘1’→’O’）。

3. 标记符号的选择：

   • 前两题用 ‘0’ 标记已访问的 ‘1’（覆盖原元素不影响结果）；
   • 本题需用矩阵中不存在的符号（如 ‘1’）作为临时标记，避免与原元素冲突，最后需恢复为 ‘O’。

三、解题思路：从边界入手，反向标记

题目拆解中也提到了这道题和前两题“地毯式搜索所有区域”的思路不同，这道题的突破口就是边缘的’O’ 里——只要挨着边缘的’O’，那它肯定没被围住，这是板上钉钉的事儿。

要是按正常思路硬刚：写个DFS去搜每个’O’，判断它是不是该被改成’X’，估计会头大到想掀桌子——我当时就卡了20多分钟，越想越乱：

• 怎么判断一个’O’到底挨没挨边界？总不能搜着搜着突然回头查坐标吧？
• 就算搜到了边界，怎么告诉上层递归“这一片都不能改”？难道要搞多个递归函数分别处理？
• 递归的终止条件更是一团乱麻：是先判断边界还是先标记？一步错步步错。

后来才反应过来：换个角度不就完了？既然边缘的’O’和它的“朋友圈”都安全，那先把它们圈出来，接下来就收拾没有被圈出来的“小可爱们”不就可以了？

核心逻辑：先标记，再清场

1. 第一步：给“边缘”贴标记
   沿着矩阵的四条边遍历，但凡看到’O’，就用DFS遍历下，把所有跟它连着的’O’都改为临时符号标记（比如改成’1’）。这些贴了标签的，都是“背景硬”的安全区，绝对不能动。

2. 第二步：大扫除，分情况处理
   再从头到尾扫一遍矩阵：
   • 没被标记的’O’：妥妥的“要被处理的”，全改成’X’；
   • 被标记的’1’：把进士标记改回去，恢复成’O’——毕竟它们本来就是O。

和前两题的思路对比：

你看，前两题是“发现一个处理一个”，这题是“先圈范围再批量处理”——思路一换，复杂题立马变简单~

四、算法实现：深度优先遍历（DFS）+ 两次遍历

基于上述思路，我们用DFS实现标记，用两次遍历完成替换。下面是具体步骤：

1. 边缘遍历：遍历矩阵的四条边（i=0、i=rows-1、j=0、j=cols-1），对每个’O’调用DFS；
2. DFS标记：在DFS中，将当前’O’标记为’1’，并递归处理上下左右四个方向的相邻’O’；
3. 全局替换：遍历整个矩阵，按规则替换字符（‘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"]
]

时间复杂度

空间复杂度

七、坑点总结

1. 边缘遍历不完整
   ❌错误：只遍历上下边缘或左右边缘，漏掉角落的’O’（如(0,0)）。
   ✅解决：必须遍历四条边（i=0、i=rows-1、j=0、j=cols-1），确保所有边缘’O’都被处理。

2. 临时标记与原字符冲突
   ❌错误：用’O’或’X’作为临时标记（如误将安全区域标记为’O’，导致无法区分）。
   ✅解决：使用矩阵中不存在的字符（如’1’、'#'等）作为临时标记，避免冲突。

3. DFS边界检查顺序
   ❌错误：先判断board[nx][ny] == 'O'，再检查坐标是否越界（可能导致访问无效坐标）。
   ✅解决：先检查坐标合法性（nx和ny是否在0_rows-1和0cols-1范围内），再判断字符是否为’O’。

4. 替换逻辑颠倒
   ❌错误：将’1’替换为’X’，将’O’替换为’O’（完全错误）。
   ✅解决：明确替换规则：'1'→'O'（恢复安全区），'O'→'X'（替换被围绕区）。

八、举一反三

掌握本题思路后，可解决以下类似问题，尤其是那些需要“反向标记”或“边界连通性判断”的场景：

1. LeetCode 417. 太平洋大西洋水流问题
   问题：找到既能流向太平洋，又能流向大西洋的所有单元格。
   思路：用本题“反向标记”的升级版——从太平洋边缘（上、左）和大西洋边缘（下、右）分别出发，标记所有能流向两大洋的单元格，最后取交集。这种“从结果倒推起点”的逻辑，与本题的反向思维如出一辙。

2. LeetCode 1020. 飞地的数量
   问题：计算无法从边界离开的陆地（‘1’）的数量。
   思路：与本题类似，先标记所有与边界相连的’1’（可离开的），再统计未标记的’1’（飞地）数量，核心是“排除法”思维。

3. LeetCode 529. 扫雷游戏
   问题：根据点击位置，展开所有无地雷的连通区域。
   思路：通过DFS/BFS从点击位置出发，按规则标记并展开区域，考验“条件递归”和“边界处理”，与本题的搜索框架高度契合。

这些问题虽场景不同，但核心都离不开“连通区域标记”和“边界特殊性利用”，掌握本题思路后，再解这些题会有种“一通百通”的感觉～

九、总结

「被围绕的区域」是连通区域问题中对“边界特殊性”考察的典型题目。它的核心思维是 “从边缘反向标记安全区域，再通过一次遍历完成状态转换”，这与前两题的“正向搜索”形成互补。

解题的关键不是记住代码，而是理解：

• 如何通过边界特征（是否接触边缘）定义区域性质；
• 如何用临时标记区分不同区域；
• 如何设计两次遍历实现原地修改。

掌握这些，你就能应对所有“基于边界的连通区域划分”问题，面试中再遇到类似题目也能游刃有余。

最后欢迎大家在评论区分享你的代码或思路，咱们一起交流探讨~ 🌟 要是有大佬有更精妙的思路或想法，恳请在评论区多多指点批评，我一定会虚心学习，并且第一时间回复交流哒！

这是封面原图～ 喜欢的话先点个赞鼓励一下呗～ 再顺手关注一波，后续更新不迷路，保证让你看得过瘾！😉