LeetCode 130中等网格 DFS
被围绕的区域 图解题解
这道题到底在问什么
给一个 m×n 矩阵 board，里面只有 "X" 和 "O"。把所有「被 X 四面围住」的 O 区域全部翻成 X。只要一片相连的 O 里有任意一格挨着矩阵边界，这一整片就是安全的，原样保留。
- 输入
- board=[["O","O","O","O","O"],["O","X","X","X","O"],["O","X","O","X","O"],["O","X","O","X","O"],["O","O","X","O","O"]]
- 输出
- 中间被围死的 (2,2)、(3,2) 两个 O 翻成 X；其余 15 个 O 都连着边界，原样保留
最优解：一步一步想明白
- 3思路一句话：别判「谁被围」，反过来从四条边的 O 出发染绿保护，剩下没染到的 O 必定被围、统统变 X。下面一步步演给你看。
- 4边界 O 共 15 个 · 从 (0,0) 起跑网格四条边上一共有 15 个 O，它们挨着边界、绝不会被围，在这个例子里还全连成一片。接下来从左上角的 (0,0) 出发（橙色高亮的就是当前访问点）做第一趟 DFS，把和它相连的 O 一路染成绿色「安全」。X（灰）是墙，染色绕不过去。
- 5已染安全 1 个从边界上的 O (0,0) 开始一趟 DFS。它本身就挨着边，铁定安全 —— 标成绿色，然后顺着它的 O 邻居继续往里钻。
- 6已染安全 2 个从 (0,0) 顺到相连的 O (1,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(1,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 7已染安全 3 个从 (1,0) 顺到相连的 O (2,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(2,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 8已染安全 4 个从 (2,0) 顺到相连的 O (3,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(3,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 9已染安全 5 个从 (3,0) 顺到相连的 O (4,0)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,0) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 10已染安全 6 个从 (4,0) 顺到相连的 O (4,1)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,1) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 11已染安全 7 个从 (0,0) 顺到相连的 O (0,1)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,1) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 12已染安全 8 个从 (0,1) 顺到相连的 O (0,2)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,2) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 13已染安全 9 个从 (0,2) 顺到相连的 O (0,3)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,3) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 14已染安全 10 个从 (0,3) 顺到相连的 O (0,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(0,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 15已染安全 11 个从 (0,4) 顺到相连的 O (1,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(1,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 16已染安全 12 个从 (1,4) 顺到相连的 O (2,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(2,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 17已染安全 13 个从 (2,4) 顺到相连的 O (3,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(3,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 18已染安全 14 个从 (3,4) 顺到相连的 O (4,4)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,4) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 19已染安全 15 个从 (4,4) 顺到相连的 O (4,3)。能从边界一路 O 连过来，说明这片 O 通到了边界，(4,3) 跟着「逃生成功」—— 染成绿色安全，继续往它的邻居钻。
- 20安全 O 15 个，被围 O 2 个所有从边界能连到的 O 都染绿了。现在扫一遍整张图：还是 O、又没被染绿的格子（红色）就是被四面 X 围死、连不到边界的 —— 它们就是要翻成 X 的「被围区域」。本例是 (2,2) (3,2)。
- 21已翻 1/2(2,2) 没被边界染到，确认被围 —— 翻成 X。被围的 O 是真的被困住了：它的四个方向要么是 X、要么是同样被困的 O，怎么都连不到边界。
- 22已翻 2/2(3,2) 没被边界染到，确认被围 —— 翻成 X。被围的 O 是真的被困住了：它的四个方向要么是 X、要么是同样被困的 O，怎么都连不到边界。
- 23保留 15 个 O，翻 2 个为 X最终结果：绿色那片 O 因为连着边界被原样保留，被围那几格变成了 X。一句话总结整道题 —— 与边界相连的 O 永远不会被围；先从四边的 O 染色保护，剩下没染到的 O 就是被围的，变 X。
⚠️ 容易写错的地方
✗ 错：对每个 O 逐个判断「它是否被围」
✓ 对：正难则反：只从边界的 O 出发染「安全」，没染到的就是被围的
「被不被围」是整片 O 的整体性质，逐格判断会把同一片反复扩展，又慢又容易错
✗ 错：DFS 起点乱选（从内部的 O 也起跑）
✓ 对：起点只取四条边上的 O
内部的 O 是否安全恰恰是要求的结论，拿它当起点等于假设了结论
✗ 错：直接把安全的 O 就地改成 X 或漏了还原
✓ 对：先用临时标记（如 #）标安全，第二趟再统一还原
不用第三种标记就分不清「已确认安全的 O」和「还没判过的 O」
完整代码（Python / C++ / Java）
Python
class Solution:
def solve(self, board):
if not board: return
R, C = len(board), len(board[0])
def dfs(i, j):
if i < 0 or j < 0 or i >= R or j >= C:
return
if board[i][j] != "O": return
board[i][j] = "#" # 标安全
dfs(i+1, j); dfs(i-1, j)
dfs(i, j+1); dfs(i, j-1)
for i in range(R): # 从四条边的 O 出发
for j in range(C):
if (i in (0, R-1) or j in (0, C-1)) \
and board[i][j] == "O":
dfs(i, j)
for i in range(R):
for j in range(C):
if board[i][j] == "O": board[i][j] = "X"
elif board[i][j] == "#": board[i][j] = "O"C++
class Solution {
public:
int R, C;
void dfs(vector<vector<char>>& b, int i, int j){
if(i<0||j<0||i>=R||j>=C) return;
if(b[i][j] != 'O') return;
b[i][j] = '#'; // 标安全
dfs(b,i+1,j); dfs(b,i-1,j);
dfs(b,i,j+1); dfs(b,i,j-1);
}
void solve(vector<vector<char>>& b){
if(b.empty()) return;
R = b.size(); C = b[0].size();
for(int i=0;i<R;i++) for(int j=0;j<C;j++)
if((i==0||i==R-1||j==0||j==C-1) && b[i][j]=='O')
dfs(b,i,j);
for(int i=0;i<R;i++) for(int j=0;j<C;j++)
if(b[i][j]=='O') b[i][j]='X';
else if(b[i][j]=='#') b[i][j]='O';
}
};Java
class Solution {
int R, C;
public void solve(char[][] board) {
if (board.length == 0) return;
R = board.length; C = board[0].length;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if ((i == 0 || i == R - 1 || j == 0 || j == C - 1)
&& board[i][j] == 'O')
dfs(board, i, j);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == '#') board[i][j] = 'O';
}
}
void dfs(char[][] b, int i, int j) {
if (i < 0 || j < 0 || i >= R || j >= C) return;
if (b[i][j] != 'O') return;
b[i][j] = '#'; // 标安全
dfs(b, i + 1, j); dfs(b, i - 1, j);
dfs(b, i, j + 1); dfs(b, i, j - 1);
}
}复杂度
时间
O(m×n)
每格最多被 DFS 访问一次，最后再整体扫一遍
空间
O(m×n)
DFS 递归栈最坏深度（一整片 O 排成长蛇时）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 被围绕的区域 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不直接判断每个 O 是否被围？+
一片 O 的「是否被围」是整体性质，单格判断要反复扩展同一片、非常费；从边界反向标安全，一趟就把所有安全 O 标完。
DFS 递归太深爆栈怎么办？+
改成显式栈的迭代 DFS，或用 BFS 队列，或并查集把所有边界 O 并到一个虚拟根上——逻辑完全等价。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 被围绕的区域 一步步讲透（全站已上线 944 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。