LeetCode 130中等网格 DFS
被围绕的区域 图解题解
这道题到底在问什么
题目：把「被 X 四面围住」的 O 翻成 X。注意是「区域」：相连的一整片 O 要么全被围、要么全安全，一格挨边整片就安全。
最优解：一步一步想明白
- 3思路一句话：别判「谁被围」，反过来从四条边的 O 出发染绿保护，剩下没染到的 O 必定被围、统统变 X。下面一步步演给你看。
- 4边界 O 共 1 个 = DFS 起点网格四条边上一共有 1 个 O（橙色），它们挨着边界、绝不会被围。接下来从每一个这样的 O 出发做 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。
完整代码（Python / C++ / Java）
Python
def solve(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(行×列)
每个格子最多被 DFS 访问一次、最后又扫一遍。时间 O(行×列)，空间 O(行×列) 是 DFS 递归栈最坏深度（一整片 O 排成长蛇时）。
空间
O(行×列)
每个格子最多被 DFS 访问一次、最后又扫一遍。时间 O(行×列)，空间 O(行×列) 是 DFS 递归栈最坏深度（一整片 O 排成长蛇时）。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 被围绕的区域 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不直接判断每个 O 是否被围？+
一片 O 的「是否被围」是整体性质，单格判断要反复扩展同一片、很费；从边界反向标安全一次就把所有安全 O 标完。
DFS 递归爆栈怎么办？+
改成显式栈或并查集，逻辑等价。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 被围绕的区域 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。