LeetCode 130中等网格 DFS
被围绕的区域 图解题解
这道题到底在问什么
把被 X 包围的 O 变成 X；连到边界的 O 保留。
- board
- [[X,X,X,X,X],[O,O,X,O,X],[X,X,X,O,X],[X,X,X,X,X]]
- 输出
- (1,3)(2,3)被围→X；(1,0)(1,1)连边界→保留
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合网格 DFS。
- 4被上下左右都是 X 围住的 O，要改成 X；而碰到边界、或和边界 O 连通的 O，要保留。例子里 (1,0)(1,1) 连到左边界要留，(1,3)(2,3) 被围要翻。
- 5正面判断「某个 O 是否被围」要绕一圈很烦。反过来：只有和边界相连的 O 才安全。先从四条边上的 O 出发 DFS，把安全的标成 S，剩下没标的 O 必然被围。
- 6扫四条边，找到左边界上的 O (1,0)。从它 DFS，把它标成 S(安全)。
- 7(1,0) 的邻居 (1,1) 也是 O、连通，所以它也安全，标 S。这一片连到了边界，整片都保住。
- 8再看 (1,3)(2,3) 这片 O：四周都是 X，DFS 从任何边界都到不了它们，没被标 S —— 它们就是被四面包围的，要翻。
- 9最后遍历整张 board：没标 S 的 O 改成 X(被围的 (1,3)(2,3))，标了 S 的恢复成 O(安全的 (1,0)(1,1))。
- 10被围区域翻成 X、和边界相连的 O 全保留。核心就是「反着想」：与其判断谁被围，不如从边界标安全、剩下的就是被围。
- 13把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：从内部 O 开始判断是否被包围
✓ 对：从边界 O 反向标记安全区
反向做更简单
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def solve(self, board):
m, n = len(board), len(board[0])
def dfs(r, c):
if r<0 or r>=m or c<0 or c>=n or board[r][c] != 'O':
return
board[r][c] = 'S' # 标记安全(连到边界)
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
for r in range(m): dfs(r,0); dfs(r,n-1) # 左右边界
for c in range(n): dfs(0,c); dfs(m-1,c) # 上下边界
for r in range(m):
for c in range(n):
board[r][c] = 'O' if board[r][c]=='S' else 'X'C++
class Solution {
public:
void solve(vector<vector<char>>& b) {
int m = b.size(), n = b[0].size();
for (int r=0;r<m;r++){ dfs(b,r,0); dfs(b,r,n-1); }
for (int c=0;c<n;c++){ dfs(b,0,c); dfs(b,m-1,c); }
for (int r=0;r<m;r++)
for (int c=0;c<n;c++)
b[r][c] = (b[r][c]=='S') ? 'O' : 'X';
}
void dfs(vector<vector<char>>& b, int r, int c) {
if (r<0||r>=(int)b.size()||c<0||c>=(int)b[0].size()||b[r][c]!='O') return;
b[r][c] = 'S';
dfs(b,r+1,c); dfs(b,r-1,c); dfs(b,r,c+1); dfs(b,r,c-1);
}
};Java
class Solution {
public void solve(char[][] b) {
int m = b.length, n = b[0].length;
for (int r=0;r<m;r++){ dfs(b,r,0); dfs(b,r,n-1); }
for (int c=0;c<n;c++){ dfs(b,0,c); dfs(b,m-1,c); }
for (int r=0;r<m;r++)
for (int c=0;c<n;c++)
b[r][c] = (b[r][c]=='S') ? 'O' : 'X';
}
void dfs(char[][] b, int r, int c) {
if (r<0||r>=b.length||c<0||c>=b[0].length||b[r][c]!='O') return;
b[r][c] = 'S';
dfs(b,r+1,c); dfs(b,r-1,c); dfs(b,r,c+1); dfs(b,r,c-1);
}
}套路模板 · 网格 DFS
# 网格 DFS 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界复杂度
时间复杂度
O(mn)
每格最多被 DFS 访问一次 + 最后扫一遍
空间复杂度
O(mn)
原地用 S 标记不开额外数组，只有 DFS 递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 被围绕的区域 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「反向从边界」更简单？+
正向判断「某 O 是否四面被围」要搜整片区域；反向只需从边界 O 一次 DFS 标记安全区，剩下就是被围的。
怎么区分安全和被围的 O？+
从边界 DFS 把安全的 O 临时标成 S；最后遍历：S 还原成 O、剩下的 O 改成 X。
复杂度？+
O(m·n)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。